5

例如，除了错误处理之外，您不会看到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)

不过，我还没有测试过最后一段代码。

4

5 回答 5

9

您可以在 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)

编辑：并将其与 augustss 的回答联系起来：

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)
于 2012-07-06T16:55:33.320 回答
9

所有的 ADT与(,), Either, (),(->)的某种组合是同构的（几乎——见结尾）VoidMu

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 数据类型是协约的，并且一直是惰性求值模型的一个批评点。您可以通过仅使用严格的求和和乘积（以及按值函数调用）并添加特殊的“惰性”数据构造函数来解决这些问题

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

然后可以忠实地编码所有同构。

于 2012-07-07T00:05:55.703 回答
7

您可以根据 定义列表Maybe，但不是这样。您的List类型不能为空。或者你是否打算Maybe (List a)成为[a]. 这似乎很糟糕，因为它不区分列表和类型。

这会起作用

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

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

于 2012-07-06T15:51:09.423 回答
1

如果它是一个列表，它应该是一个实例Functor，对吧？

instance Functor List
  where fmap f (List a as) = List (f a) (mapMaybeList f as)

mapMaybeList :: (a -> b) -> Maybe (List a) -> Maybe (List b)
mapMaybeList f as = fmap (fmap f) as

这里有一个问题：你可以创建List一个 的实例Functor，但你的 Maybe List 不是：即使它本身Maybe还不是一个实例Functor，你也不能直接将一个构造像Maybe . List任何东西的实例（你需要包装器类型）。

对于其他类型类也是如此。

话虽如此，使用您的公式，您可以做到这一点，而标准 Haskell 列表则无法做到这一点：

instance Comonad List
  where extract (List a _) = a
        duplicate x @ (List _ y) = List x (duplicate y)

不过，Maybe List 仍然不会是comonadic。

于 2012-07-06T17:48:36.857 回答
1

当我第一次开始使用 Haskell 时，我也尝试尽可能多地用现有类型表示事物，因为避免冗余是件好事。我目前的理解（移动目标！）倾向于更多地涉及多维权衡网络的想法。我不会在这里给出任何“答案”，而是粘贴示例并询问“你明白我的意思吗？” 无论如何，我希望它有所帮助。

让我们看一下 Darcs 代码：

data UseCache = YesUseCache | NoUseCache
    deriving ( Eq )

data DryRun = YesDryRun | NoDryRun
    deriving ( Eq )

data Compression = NoCompression
                 | GzipCompression
    deriving ( Eq )

您是否注意到这三种类型都可能是Bool's？为什么你认为 Darcs 黑客决定他们应该在他们的代码中引入这种冗余？再举一个例子，这是我们几年前更改的一段代码：

type Slot = Maybe Bool                  -- OLD code
data Slot = InFirst | InMiddle | InLast -- newer code

为什么你认为我们认为第二个代码是对第一个代码的改进？

最后，这是我日常工作中的一些代码。它使用newtypeaugustss提到的语法，

newtype Role = Role { fromRole :: Text }
  deriving (Eq, Ord)

newtype KmClass = KmClass { fromKmClass :: Text }
  deriving (Eq, Ord)

newtype Lemma = Lemma { fromLemma :: Text }
  deriving (Eq, Ord)

在这里，您会注意到我做了一件奇怪的事情，即采用一个非常好的Text类型，然后将它包装成三个不同的东西。与普通的 old 相比，这三件事没有任何新功能Text。他们只是为了与众不同。老实说，我不完全确定这样做对我来说是否是个好主意。我暂时认为这是因为我出于多种原因操纵了许多不同的文本片段，但时间会证明一切。

你能看出我想表达什么吗？

于 2012-07-07T05:56:28.067 回答