为` `Cons a`实现`concat`

Question

我正在看一个实现instance Monad []的练习。但是，考虑到以下定义，我想实现Monad Cons：

data Cons a = Cons a (Cons a) | Empty

我试图实现等同于concat的东西，但我称它为flatten

flatten :: Cons (Cons a) -> Cons a
flatten Empty                  = Empty
flatten (Cons c@(Cons _ _) xs) = ...

但后来我对[a]如何映射到Cons a (Cons a)感到困惑。

请给我一个提示，让我编写flatten的其余部分。

Answer 1

这实际上非常简单。concat函数通常定义如下：

concat :: [[a]] -> [a]
concat = foldr (++) []

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ a []     = a
foldr f a (x:xs) = f x (foldr f a xs)

(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : xs ++ ys

让我们分别调用这些函数的Cons版本flatten、reduceR和append：

flatten :: Cons (Cons a) -> Cons a
flatten = reduceR append Empty

reduceR :: (a -> b -> b) -> b -> Cons a -> b
reduceR _ a Empty       = a
reduceR f a (Cons x xs) = f x (reduceR f a xs)

append :: Cons a -> Cons a -> Cons a
append Empty       ys = ys
append (Cons x xs) ys = Cons x (append xs ys)

与我使用的@jamshidh不同，我使用的是右折叠而不是左折叠，因为(++)的实现方式，a ++ (b ++ c)在计算上比(a ++ b) ++ c更便宜。

现在我们可以让Cons成为Monad的一个实例，如下所示：

instance Functor Cons where
    fmap _ Empty       = Empty
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)

instance Monad Cons where
    return a = Cons a Empty
    m >>= f = flatten (map f m)

很简单。接下来，尝试使Cons成为Applicative和Alternative的实例。

Answer 2

为了防止我的大脑爆炸，我首先要定义一个组合两个Cons a项的函数

consPlus::Cons a->Cons a->Cons a
consPlus Empty x = x
consPlus (Cons x rest) y = Cons x (consPlus rest y)

然后，我将定义foldl的Cons a版本

consFoldl::(b->a->b)->b->Cons a->b
consFoldl f init Empty = init
consFoldl f init (Cons x rest) = consFoldl f (f init x) rest

然后，最后以显而易见的方式将其扩展为连接

consConcat = consFoldl consPlus Empty

另一种避免头脑爆炸的技术是这样定义Cons a

data Cons a = a ::: Cons a | Empty
infixr 8 :::

不同之处在于语法，但更易于阅读

(1:::2:::Empty):::(3:::Empty):::Empty

比这更好

Cons (Cons 1 (Cons 2 Empty)) (Cons (Cons 3 Empty) Empty)