内部表現から計算式の結果を求める

Question

###実現したいこと
変数の値のリストと，内部表現にによる式を与え，その計算式の値を求める．
この値を求める関数をevalとする．
(例)
eval [("x",4);("y",3)] (Mul(Mul(Var "x", Var "y"),Add(Var "x",Num 3)));;

• : int = Some 84

###現状のコード

type exp =
  | Num of int 
  | Var of string 
  | Add of exp * exp 
  | Mul of exp * exp;;

let make_sum a1 a2 = Add (a1,a2);;

let make_product m1 m2 = Mul (m1,m2);;

let rec assoc x list =
    match list with
    |[] -> None
    |(a,b)::t -> if a = x then Some b 
                 else assoc x t;;

let calc var =
    match var with
    | Add (Num x, Num y) -> x+y
    | Mul (Num x, Num y) -> x*y;;

let rec eval list var =
    match var with
    |Num n -> n
    |Var x -> assoc (x list)
    |Add (x, y) -> calc calc (eval (var));;

let rec do_string_of_exp  var judge =
  match var with
  | Num n -> string_of_int n
  | Var x -> x
  | Add (x, y) -> if judge=1 then "(" ^ do_string_of_exp (x) 0 ^ "+" ^ do_string_of_exp (y) 0 ^")"
                  else do_string_of_exp (x) 0 ^ "+" ^ do_string_of_exp (y)  0
  | Mul (x, y) -> do_string_of_exp (x) 1 ^ "*" ^ do_string_of_exp (y) 1;;

let string_of_exp var =
    do_string_of_exp var 0;;

###以上のコードをuse "～.ml"を用いて使用しようとした結果

type exp = Num of int | Var of string | Add of exp * exp | Mul of exp * exp
val make_sum : exp -> exp -> exp = <fun>
val make_product : exp -> exp -> exp = <fun>
val assoc : 'a -> ('a * 'b) list -> 'b option = <fun>
File "ex3_3.ml", line 18, characters 4-84:
18 | ....match var with
19 |     | Add (Num x, Num y) -> x+y
20 |     | Mul (Num x, Num y) -> x*y..
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(Add (Num _, (Var _|Add (_, _)|Mul (_, _)))|
Add ((Var _|Add (_, _)|Mul (_, _)), _)|
Mul (Num _, (Var _|Add (_, _)|Mul (_, _)))|
Mul ((Var _|Add (_, _)|Mul (_, _)), _)|Num _|Var _)
val calc : exp -> int = <fun>
File "ex3_3.ml", line 25, characters 21-22:
25 |     |Var x -> assoc (x list)
                          ^
Error: This expression has type string
       This is not a function; it cannot be applied.

###質問したい内容
Warningの分岐条件が足りてないというものは一度置いておいて．
25行目のxにを注意されていることが良くわかりません．
僕のなかでは，assocの第一引数は文字列であるとしているのですが，なぜここが関数でないからといってエラーが発生するのでしょうか．

assocという関数は連想リストを検索して，存在したらその値を，なかったらNoneを返すというものにしています．
assoc 4 [(2,"two"); (3,"three"); (5,"five")];;
これならばNoneが返る．

###追記
現状このようになっています．
しかしまだエラーが出てきます．コードの下にエラーを示します．

type exp =
  | Num of int 
  | Var of string 
  | Add of exp * exp 
  | Mul of exp * exp;;

let make_sum a1 a2 = Add (a1,a2);;

let make_product m1 m2 = Mul (m1,m2);;

let rec assoc x ls =
    match ls with
    |[] -> None
    |(a,b)::t -> if a = x then Some b 
                 else assoc x t;;

let calc var =
    match var with
    | Add (Num x, Num y) -> Some (x+y)
    | Mul (Num x, Num y) -> Some (x*y);;

let rec eval ls var =
    match var with
    |Num n -> Some n
    |Var x -> assoc x ls
    |Add (x, y) -> calc Add ( eval ls Some x, eval ls Some y )
    |Mul (x, y) -> calc Mul ( eval ls Some x, eval ls Some y );;

####エラー

type exp = Num of int | Var of string | Add of exp * exp | Mul of exp * exp
val make_sum : exp -> exp -> exp = <fun>
val make_product : exp -> exp -> exp = <fun>
val assoc : 'a -> ('a * 'b) list -> 'b option = <fun>
File "ex3_3.ml", line 18, characters 4-98:
18 | ....match var with
19 |     | Add (Num x, Num y) -> Some (x+y)
20 |     | Mul (Num x, Num y) -> Some (x*y)..
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(Add (Num _, (Var _|Add (_, _)|Mul (_, _)))|
Add ((Var _|Add (_, _)|Mul (_, _)), _)|
Mul (Num _, (Var _|Add (_, _)|Mul (_, _)))|
Mul ((Var _|Add (_, _)|Mul (_, _)), _)|Num _|Var _)
val calc : exp -> int option = <fun>
File "ex3_3.ml", line 26, characters 19-23:
26 |     |Add (x, y) -> calc Add ( eval ls Some x, eval ls Some y )
                        ^^^^
Error: This function has type exp -> int option
       It is applied to too many arguments; maybe you forgot a `;'.

Answer 1

(x list)とカッコがついているのでxが関数と推論されているのでは？

---

assoc x listにすると型が合わないと怒られる問題について:

type exp =
  | Num of int 
  | Var of string 
  | Add of exp * exp 
  | Mul of exp * exp;;

//...

let rec eval list var =
    match var with
    |Num n -> n
    |Var x -> assoc x list
    |Add (x, y) -> calc calc (eval (var));;

とあるので evalの最初のパターンマッチの返り値nはintですが、
その次の返り値 assoc x listの型は'a optionと何かしらのオプション型なので
型が全然合ってません。

問題文を見ると、

eval [("x",4);("y",3)] (Mul(Mul(Var "x", Var "y"),Add(Var "x",Num 3)));;

: int = Some 84

なのですから evalの返り値はint optionとすべきですね。
つまり|Num n -> nの時点でもう型が違います。

とりあえず(全部消してイチから)全部の関数に型を明示して書いてはどうでしょう。

---

文法が似ているF#で書いてみました

open System


type Exp =
    | Num of int 
    | Var of string 
    | Add of Exp * Exp 
    | Mul of Exp * Exp


// let hoge = Mul(Num 3, Var "x") // OK

type VarValuePair = string * int


let rec assoc (name : string) (pairs : VarValuePair list) : int option =
    match pairs with
    | [] -> None
    | (var, value)::t -> 
        if var = name then Some value 
        else assoc name t

let rec eval (pairs : VarValuePair list) (exp : Exp): int option =
    match exp with
    | Num x -> Some x
    | Var var -> assoc var pairs
    | Add (x, y) -> 
        let x = (eval pairs x)
        let y = (eval pairs y)
        match (x, y) with
        | (Some x, Some y) -> Some (x+y)
        | _ -> None
    | Mul (x, y) ->
        let x = (eval pairs x)
        let y = (eval pairs y)
        match (x, y) with
        | (Some x, Some y) -> Some (x*y)
        | _ -> None


[<EntryPoint>]
let main argv =

    let result = eval [("x",4); ("y",3)] (Mul(Mul(Var "x", Var "y"),Add(Var "x",Num 3)))
    printfn "%A" result
    0 // return an integer exit code

Comments

[grape_ll]

括弧がつくと関数扱いを受けるのはなぜなのか，解説していただくことは出来ますでしょうか．
また，()を外してみたところ．

# #use "ex3_3.ml";;
type exp = Num of int | Var of string | Add of exp * exp | Mul of exp * exp
val make_sum : exp -> exp -> exp = <fun>
val make_product : exp -> exp -> exp = <fun>
val assoc : 'a -> ('a * 'b) list -> 'b option = <fun>
File "ex3_3.ml", line 18, characters 4-84:
18 | ....match var with
19 | | Add (Num x, Num y) -> x+y
20 | | Mul (Num x, Num y) -> x*y..
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(Add (Num _, (Var _|Add (_, _)|Mul (_, _)))|
Add ((Var _|Add (_, _)|Mul (_, _)), _)|
Mul (Num _, (Var _|Add (_, _)|Mul (_, _)))|
Mul ((Var _|Add (_, _)|Mul (_, _)), _)|Num _|Var _)
val calc : exp -> int = <fun>
File "ex3_3.ml", line 25, characters 14-26:
25 | |Var x -> assoc x list
^^^^^^^^^^^^
Error: This expression has type 'a option
but an expression was expected of type int
このように別のエラーになってしまうようです．
文字列で検索を掛けたいのでint型に治したくはないのですが，どのようにすればよいでしょうか．

[ozwk]

assoc (x list) と書いたら、
let y = x list
assoc y
と同等の意味になります
x list と書いたからには x に引数 list を渡していることになるので
すなわちxは関数であるはず。となります。

[grape_ll]

関数の引数に括弧をつけるのが自然な流れだと感じでいるのつけてしまったのですが，ocamlでは意味が変わってしまうのですね．ありがとうございます．
型の明示をしてみたところ，うまく明示できていないのか，他のところで問題が起き始めてしまったので，断念してしまったのですが，教えていただいたF#を拙いながらも読んで参考にさせていただきながら自分のコードを変更しました．質問内容の追記に載せていただきます．
しかし，引数の数がおかしいというエラーが生じてしまいました．　Add()一つしか渡していないように思うのですが，なぜ数がおかしいと言われているのでしょうか．

[ozwk]

calc Add (...)は
calc にAdd と (...)を渡していることになります

calc (Add (...))です

[grape_ll]

このAddはAdd of exp * exp のものだと私は想定していて，このときはAdd (...)で1つのものになると思っていたのですが，なぜそう受け取られないのか，理由などはございますでしょうか．

また，calc (Add (..))としたところ，
26 | |Add (x, y) -> calc (Add ( eval ls Some x, eval ls Some y ))
　　　　 ^^^^
Error: This function has type (string * int) list -> exp -> int option
It is applied to too many arguments; maybe you forgot a `;'.
となり，これも同じ理由だと考え，
calc (Add ( eval ls (Some x), eval ls (Some y) ))
としたのですが

26 | |Add (x, y) -> calc (Add ( eval ls (Some x), eval ls (Some y) ))
　　　　　^^^^
Error: This variant expression is expected to have type exp
The constructor Some does not belong to type exp
となってしまいました．
Someは何が入ってもいいというような認識でいたのですが，type expに属していないといわれているので，
|Add (x, y) ->
のあとに16通りのx, yのマッチングを記述しなくてはいけないのでしょうか．

[ozwk]

> 型の明示をしてみたところ，うまく明示できていないのか，他のところで問題が起き始めてしまった

型を明示して起こる問題は、型を明示しなかったらよりわかりにくい形で現れるだけです。
書きましょう。

さてともかく

> Add (x, y) -> calc (Add ( eval ls (Some x), eval ls (Some y) ))

Add of exp * expですから xとyはexpですね。

eval ls (Some x)は lsが多分(string * int)で(Some x)は exp optionですね。
一方eval は 型が明示してありませんが
(string * int) list -> exp -> int optionでしょう。

となると型があってませんね。expを渡すべきところをexp optionを渡しています

[grape_ll]

exp とexp optionの違いが良くわかっていない状態でして，
exp optionはexpの中身でNumやvalのことでしょうか．

直すために，Addがexp*expならば，evalの引数にそのままxを入れて
|Add (x, y) -> calc (Add ( eval ls x, eval ls y ))
のようにすればよいのではないかと思ったのですが．

26 | |Add (x, y) -> calc (Add ( eval ls x, eval ls y ))
　　　　 ^^^^^^
Error: This expression has type int option
but an expression was expected of type exp
となってしまい，確かにeval関数はint optionを返しているなというのは読み取れるのですが，そうなるとevalを再帰的に用いてAdd()を見ていくことが出来ないということになってしまうように思われます．
なにか対象法等はありますでしょうか．

[grape_ll]

let add (Some x, Some y) =
Some (x + y);;

let mul (Some x, Some y) =
Some (x * y);;

let rec eval ls var =
match var with
|Num n -> Some n
|Var x -> assoc x ls
|Add (x, y) -> add ( eval ls x, eval ls y )
|Mul (x, y) -> mul ( eval ls x, eval ls y );;

このようにしましたら
# eval [("x",4);("y",3)] (Mul(Mul(Var "x", Var "y"),Add(Var "x",Num 3)));;
- : int option = Some 84
このようになったのですが，これは力業すぎますでしょうか．

[ozwk]

> exp とexp optionの違いが良くわかっていない状態でして，

そこからですか...
'a optionは Some of 'a | Noneのことです。

> 確かにeval関数はint optionを返しているなというのは読み取れるのですが，そうなるとevalを再帰的に用いてAdd()を見ていくことが出来ないということになってしまうように思われます．

「Add(x,y)をevalする際に、 x(またはy)のevalがNoneだったらどうあるべきか」を考えてください。
Add(x, y)のevalは x, y のeval結果が両方ともSomeである場合はSome (和)、そうでなければNoneとするのが適当でしょう。

[ozwk]

> 力業すぎますでしょうか
Warningでません?

[grape_ll]

optionについて，定義的に理解することは出来たような気がします．ありがとうございます．

Noneに対応するため．
let add (Some x, Some y) =
if x = None then None
else if y = None then None
else Some (x + y);;
としてみたのですが，こうすると
25 | else Some (x + y);;
　　 ^
Error: This expression has type 'a option
but an expression was expected of type int
となってしまいます，なせ条件分岐を付けただけでintであると期待されてしまうのでしょうか．

warningは出ますが，計算自体は問題ないようです
リストにない文字を用いるとexeptionを出してしまうのがocamlらしいものではないと思いますが，それいがは特に問題のある計算例を見つけられていません．

[ozwk]

> リストにない文字を用いるとexeptionを出してしまう

はい、それが問題です。

add がSome x, Some yで受けてるのでNone来たらどうすんの？ってことです。

add をSome xで受けずにxで受けるようにして中でSome Noneを場合分けしてください

[grape_ll]

let add (x, y) =
match x with
|None -> None
|Some x -> match y with
|None -> None
|Some y -> Some (x + y);;

let mul (x, y) =
match x with
|None -> None
|Some x -> match y with
|None -> None
|Some y -> Some (x + y);;

let rec eval ls var =
match var with
|Num n -> Some n
|Var x -> assoc x ls
|Add (x, y) -> add ( eval ls x, eval ls y )
|Mul (x, y) -> mul ( eval ls x, eval ls y );;

のようにしたら
# eval [("x",2);("y",3)] (Mul(Mul(Add(Var "x", Var "z"), Var "y"),Add(Var "x",Num 3)));;
- : int option = None
となって望んでいるような形で帰ってきました．

[ozwk]

お疲れ様でした

[grape_ll]

とても丁寧に手助けしていただきありがとうございました．