一般来说，可折叠仿函数是否有等同于 head/tail 的东西？

Question

我想表达以下 Haskell 代码，仅使用 函子代数 （即 - 不依赖任何具体容器类型，如List):

ys = zipWith (+) (head xs : repeat 0)
                 (tail xs ++ [y])

我觉得应该有办法做到这一点，只依靠Foldable（或者，也许，Traversable），但我看不到。

我在想：

Foldable/Traversable 仿函数有 first 和 rest 的一般概念吗？
是否有一种公认的惯用方法，仅使用函子代数来移动 Foldable/Traversable 函子的内容？（请注意，上面的计算可能用英语描述为 "Shift in one value from the right, and add back the value that falls of on the left to the new first value."）

Answer 1

您可以使用来自 Data.Monoid 的 First 或 Last 幺半群找到 Foldable 的第一个或最后一个元素。

foldMap (Last . Just)  :: Foldable t => t a -> Last a
foldMap (First . Just) :: Foldable t => t a -> First a

所有 Foldable 都可以转换为列表，因此因为您可以找到列表的头部和尾部，所以您可以对任何 Foldable.

执行此操作

toList = foldr (:) [] :: Foldable t => t a -> [a]

就是说，尾部将有一个列表类型，而不是 Foldable 的列表类型（除非它也是一个列表）。这最终是因为并非所有 Foldable 都可以实现 uncons。例如：

data Pair a = Pair a a

这是 Foldable，但您无法使用 Pair.

表示 Pair 的尾部

Answer 2

您问题的第一部分（将结构的第一个值与一个事物组合，其余部分保持不变）可以使用 Traversable 以直接的方式完成。我们将使用 State，从我们要应用的功能开始，然后立即将其修改为 id。

onlyOnHead :: Traversable t => (a -> a) -> t a -> t a
onlyOnHead f xs = evalState (traverse go xs) f where
    go x = do
        fCurrent <- get
        put id
        return (fCurrent x)

您可以用类似的想法旋转元素：我们将旋转一个列表，并将其填充到我们的 State 中作为从中绘制元素的东西。

rotate :: Traversable t => t a -> t a
rotate xs = evalState (traverse go xs) (rotateList (toList xs)) where
    rotateList [] = []
    rotateList vs = tail vs ++ [head vs]

    go _ = do
        v:vs <- get
        put vs
        return v

Answer 3

感谢所有回复的人！

请注意，Conal Elliott's shaped-types library 在这方面也有一些有用的机制。

Answer 4

要旋转，您不需要任何丑陋的偏函数。这个奇怪的 Applicative 可以解决问题。

data Foo a t where
  Cons :: (a -> q -> t) -> a -> Foo a q -> Foo a t
  Nil :: t -> Foo a t

instance Functor (Foo a) where
  fmap f (Cons g x xs) = Cons (\p q -> f (g p q)) x xs
  fmap f (Nil q) = Nil (f q)

instance Applicative (Foo a) where
  pure = Nil
  liftA2 f (Nil t) ys = f t <$> ys
  liftA2 f (Cons g x xs) ys = Cons (\a (q,b) -> f (g a q) b) x (liftA2 (,) xs ys)

你可以旋转一个 Foo:

rot :: Foo a t -> Foo a t
rot n@(Nil _) = n
rot (Cons g0 a0 as0) = go g0 a0 as0
  where
    go :: (a -> q -> t) -> a -> Foo a q -> Foo a t
    go g a n@(Nil _) = Cons g a n
    go g a (Cons h y ys) = Cons g y (go h a ys)

和运行一个得到结果：

runFoo :: Foo a t -> t
runFoo (Nil t) = t
runFoo (Cons g x xs) = g x (runFoo xs)

综合起来，

rotate :: Traversable t => t a -> t a
rotate = runFoo . rot . traverse (\a -> Cons const a (Nil ()))

然后rotate [1..10] = [2..10] ++ [1].

一般来说，可折叠仿函数是否有等同于 head/tail 的东西？

Is there an equivalent to head/tail for Foldable functors in general?

haskell

functor

shift

traversable

foldable