Соответствующий элемент в абстрактном типе данных в OCaml

Question

Я новичок в OCaml. Сейчас я практикую некоторые из моих кодов. Я только что проверил свой пользовательский тип данных (я не думаю, что это действительно «мой» пользовательский), но я столкнулся с ошибкой. Это код

type btree =
  | Empty
  | Node of (int * btree * btree)

let rec mem : int -> btree -> bool
= fun n t ->
  match t with
    |Empty -> false
    |Node (a,b,c) -> if a = n then true
                     else if mem n b then true
                     else if mem n c then true;;

OCaml говорит, что последнее 'true;должен быть типом unit, но я планировал, что эта функция mem должна возвращать логическое значение. Я не понимаю, почему 'true' не подходит для него ... Кстати, функция mem предназначена для проверки того, что btree 't' содержит int 'n'.

Answer 1

OCaml имеет две формы выражения if:

if <cond> then <exp1> else <exp2>

и

if <cond> then <exp1>

В последней форме ветвь else опущена и по умолчанию else () где () - значение единицы измерения. Другими словами, последняя форма является синтаксическим сахаром

if <cond> then <exp1> ::= if <cond> then <exp1> else ()

Поэтому, когда вы пишете, например,

if friendly then "Say hello"

, она совпадает с

if friendly then "Say hello" else ()

Это выражение не правильно сформировано, поскольку в зависимости от условия (friendly) оно может возвращать либо значение типа string, либо значение типа unit. В OCaml каждое выражение должно иметь один и только один тип.

Переходя к вашему коду, в частности, у вас есть цепочка выражений if/then/else, а последнее выражение else опущено, возможно, потому что вы чувствовали, что по умолчанию оно должно быть false (это некейс). Семантически правильная версия вашего кода:

if a = n then true
else if mem n b then true
else if mem n c then true
else false

Однако этот код можно улучшить. В OCaml (||) и (&&) операторы имеют короткое замыкание, т. Е. В x || y выражение y не вычисляется, если x истинно. Поэтому, когда у нас есть выражение в виде

 if <cond> then true else <bool-expr>

, мы всегда можем переписать его более кратким (и более простым для понимания)

 <cond> || <bool-expr>

, следовательно, ваш код может быть переписан в

a = n || mem n b || mem n c 

, что намного короче, проще для понимания и менее подвержено ошибкам.