列表在Haskell中定义为Maybe？为什么不？

Question

Maybe List除了错误处理之外,你不会看到它,因为列表Maybe本身有点:它们有自己的" Nothing":[]和它们自己的" Just": (:). 我使用Maybe和函数编写了一个列表类型,将标准转换为"实验"列表.toStd . toExp == id.

data List a = List a (Maybe (List a))
    deriving (Eq, Show, Read)

toExp [] = Nothing
toExp (x:xs) = Just (List x (toExp xs))

toStd Nothing = []
toStd (Just (List x xs)) = x : (toStd xs)

您如何看待它,作为减少重复的尝试,概括一下？

树也可以使用这些列表定义:

type Tree a = List (Tree a, Tree a)

不过,我还没有测试过最后一段代码.

Answer 1

您可以在Haskell中以多种方式定义列表.例如,作为功能:

{-# LANGUAGE RankNTypes #-}

newtype List a = List { runList :: forall b. (a -> b -> b) -> b -> b }

nil :: List a
nil = List (\_ z -> z )

cons :: a -> List a -> List a
cons x xs = List (\f z -> f x (runList xs f z))

isNil :: List a -> Bool
isNil xs = runList xs (\x xs -> False) True

head :: List a -> a
head xs = runList xs (\x xs -> x) (error "empty list")

tail :: List a -> List a
tail xs | isNil xs = error "empty list"
tail xs = fst (runList xs go (nil, nil))
    where go x (xs, xs') = (xs', cons x xs)

foldr :: (a -> b -> b) -> b -> List a -> b
foldr f z xs = runList xs f z

这个实现的技巧是列表被表示为执行列表元素折叠的函数:

fromNative :: [a] -> List a
fromNative xs = List (\f z -> foldr f z xs)

toNative :: List a -> [a]
toNative xs = runList xs (:) []

在任何情况下,真正重要的是在合同(或法律)的类型和其运作遵循和性能实现的.基本上,任何履行合同的实现都会为您提供正确的程序,更快的实现将为您提供更快的程序.

什么是名单合同？好吧,我不打算详细地表达它,但列出服从这样的陈述:

1. head (x:xs) == x
2. tail (x:xs) == xs
3. [] == []
4. [] /= x:xs
5. 如果xs == ys和x == y,那么x:xs == y:ys
6. foldr f z [] == z
7. foldr f z (x:xs) == f x (foldr f z xs)

编辑:并将此与奥古斯特的答案联系起来:

newtype ExpList a = ExpList (Maybe (a, ExpList a))

toExpList :: List a -> ExpList a
toExpList xs = runList xs (\x xs -> ExpList (Just (x, xs))) (ExpList Nothing)

foldExpList f z (ExpList Nothing) = z
foldExpList f z (ExpList (Just (head, taill))) = f head (foldExpList f z tail)

fromExpList :: ExpList a -> List a
fromExpList xs = List (\f z -> foldExpList f z xs)

Answer 2

所有的抽象数据类型是同构的(几乎是-见端)的组合(,),Either,(),(->),Void和Mu在那里

data Void --using empty data decls or
newtype Void = Void Void

并Mu计算仿函数的固定点

newtype Mu f = Mu (f (Mu f))

所以例如

data [a] = [] | (a:[a])

是相同的

data [a] = Mu (ListF a)
data ListF a f = End | Pair a f

它本身就是同构的

newtype ListF a f = ListF (Either () (a,f))

以来

data Maybe a = Nothing | Just a

是同构的

newtype Maybe a = Maybe (Either () a)

你有

newtype ListF a f = ListF (Maybe (a,f))

这可以在mu中内联

data List a = List (Maybe (a,List a))

和你的定义

data List a = List a (Maybe (List a))

只是Mu的展开和外部的Maybe的消除(对应于非空列表)

你完成了......

几件事

1. 使用自定义ADT可提高清晰度和类型安全性

2. 这种普遍性很有用:参见GHC.Generic

好吧,我说的几乎是同构的.事实并非如此

hmm = List (Just undefined)

在[a] = [] | (a:[a])列表的定义中没有等价值.这是因为Haskell数据类型是共同的,并且一直是对懒惰评估模型的批评.您可以通过仅使用严格的总和和产品(以及通过值函数调用)以及添加特殊的"Lazy"数据构造函数来解决这些问题

data SPair a b = SPair !a !b
data SEither a b = SLeft !a | SRight !b
data Lazy a = Lazy a --Note, this has no obvious encoding in Pure CBV languages,
--although Laza a = (() -> a) is semantically correct, 
--it is strictly less efficient than Haskell's CB-Need 

然后所有的同构都可以忠实地编码.

Answer 3

你可以用Maybe,但不是那样定义列表.你的List类型不能为空.或者你打算Maybe (List a)成为替代者[a].这看起来很糟糕,因为它不区分列表和类型.

这会奏效

newtype List a = List (Maybe (a, List a))

这有一些问题.首先使用它会比通常的列表更冗长,其次,域名与列表不同构,因为我们在那里有一对(可以是未定义的;在域中添加额外的级别).