Есть ли язык типа ml (стандартный ml / ocaml / f # / haskell / etc), в котором элементы списка являются типами опций

Question

Мне кажется, что [] (пустой список) и None / Nothing так похожи.Мне было интересно, если какой-либо из этого семейства языков имеет базовый тип списка, где каждый элемент является опцией, а хвостовая часть - это Ничто?

Это (не так, в языках с разными типами), потому что это делает списки сопоставления с образцом слишком многословными?

Answer 1

У вас есть что-то похожее в Лиспе, где nil используется для представления как отсутствия необязательного значения, так и пустого списка. Вы можете сделать что-то подобное в Haskell (и я предполагаю, что большинство ML-подобных языков),

newtype MyList a = MyList (Maybe (a, MyList a))

но он более многословен и не имеет очевидных преимуществ по сравнению с использованием собственного типа данных.

Answer 2

Хм, не то, чтобы я знал. Это было бы трудно для системы типов Хиндли-Милнера, которая лежит в основе систем типов для этих языков. (В номенклатуре Haskell) Nothing должен иметь одновременно тип Maybe a и [] a.

Нечто подобное (но, к сожалению, слишком громоздкое для использования на практике IMO) может быть построено с использованием типа с фиксированной точкой над Maybe:

-- fixed point
newtype Mu f = In (f (Mu f))
-- functor composition
newtype (f :. g) a = O (f (g a))

type List a = Mu (Maybe :. (,) a)

Это изоморфно тому, что вы просите, но это боль в заднице. Мы можем легко сделать функцию "против":

In (O (Just (1, In (O (Just (2, In (O Nothing)))))))

In и O являются «конструкторами идентичности» - они существуют только для проверки типов, поэтому вы можете мысленно удалить их и получить то, что хотите. Но, к сожалению, вы не можете физически удалить их.

Мы можем легко сделать функцию cons. Нам не так повезло с сопоставлением с образцом. Я не могу говорить за другие языки семейства ML, но IIRC они не могут даже представлять более родственные типы, такие как Mu.