Haskell中的递归方案,用于反复将数据类型分解为"head"和"tail"并产生结果结构

Question

在Haskell中,我最近发现以下函数很有用:

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

我用它从列表中生成大小为3的滑动窗口,如下所示:

*Main> listCase (\_ -> take 3) [1..5]
[[2,3,4],[3,4,5],[4,5],[5],[]]

是否有更一般的递归方案来捕获这种模式？更具体地说,这允许您通过反复将数据分成"头部"和"尾部"来生成某种结果结构？

Answer 1

你要求的是一个comonad.这可能听起来比monad更可怕,但是更简单的概念(YMMV).

Comonads是具有附加结构的Functors:

class Functor w => Comonad w where
    extract :: w a -> a
    duplicate :: w a -> w (w a)
    extend :: (w a -> b) -> w a -> w b

(extend并且duplicate可以相互定义)和类似于monad法律的法律:

duplicate . extract = id
duplicate . fmap extract = id
duplicate . duplicate = fmap duplicate . duplicate

具体来说,签名(a -> [a] -> b)采用非空类型列表a.通常的类型[a]不是comonad的实例,但非空列表是:

data NE a = T a | a :. NE a deriving Functor

instance Comonad NE where
   extract (T x) = x
   extract (x :. _) = x
   duplicate z@(T _) = T z
   duplicate z@(_ :. xs) = z :. duplicate xs

comonad法则仅允许此实例用于非空列表(实际上是第二个).

然后你的功能变成了

extend (take 3 . drop 1 . toList)

哪里toList :: NE a -> [a]显而易见.这比原始更糟糕,但是=>>如果重复应用,则可以编写更简单的扩展.

有关详细信息,您可以从Haskell中的Comonad类型类开始？.