5

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

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

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

我在想：

  1. 可折叠/可遍历函子是否有先和后退的一般概念？
  2. 是否有一种公认的惯用方式，仅使用函子代数来移动可折叠/可遍历函子的内容？（请注意，上面的计算可能用英语描述为“从右侧移入一个值，并将落在左侧的值加回新的第一个值。”）
4

4 回答 4

6

Foldable您可以使用 中的First或Lastmonoids找到 a 的第一个或最后一个元素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 来表示 a 的尾部Pair。

于 2018-06-10T15:42:05.860 回答
4

您问题的第一部分（将结构的第一个值与一件事结合起来，其余部分保持不变）可以用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
于 2018-06-10T16:06:36.510 回答
1

要旋转，您不需要任何丑陋的偏函数。这个奇怪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]。

于 2018-06-11T21:48:41.100 回答
0

感谢所有回复的人！

请注意，Conal Elliott 的 shape-types 库在这方面也有一些有用的机制。

于 2018-06-11T14:59:56.493 回答