一般来说,可折叠仿函数的头/尾是否等同？

Question

我想表达以下Haskell代码,仅使用函子代数(即 - 不依赖于任何特定的容器类型,例如List):

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

在我看来,应该有一种方法来做到这一点,只依靠Foldable(或者,也许Traversable),但我看不到它.

我在想:

1. 是否有一个一般概念第一和休息的折叠/ Traversable的函子？
2. 有没有一种公认的方法,只使用函子代数,来移动可折叠/可遍历仿函数的内容？(请注意,上面的计算可能用英语描述为"从右侧移入一个值,并将左侧的值添加回新的第一个值.")

Answer 1

你可以找到Foldable使用First或者Lastmonoids 的第一个或最后一个元素Data.Monoid.

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使用a 的尾巴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