代码之家 › 专栏 › 技术社区 › dbanas

折叠式函子的头/尾一般是等价的吗?

foldable traversable shift functor haskell

dbanas · 技术社区 · 7 年前

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

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

在我看来,应该有办法做到这一点,仅仅依靠 Foldable (或者,也许, Traversable ,但我看不见。

我想知道:

有没有一个普遍的概念第一和休息对于可折叠/可遍历函子?
是否有一种公认的惯用方法,仅使用函子代数,来转移可折叠/可遍历函子的内容? (注意,上面的计算可以用英语描述为“从右边移一个值,然后将左边的值加回到新的第一个值。”)

4 回复 | 直到 7 年前

Daniel Wagner 7 年前

问题的第一部分(将一个结构的第一个值与一件事合并,其余的保持不变)可以用 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)

你可以用一个类似的想法旋转元素:我们将旋转一个列表,并在我们的东西。 状态 从中提取元素。

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

erisco 7 年前

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

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

所有 可折叠的 可转换为一个列表,因此,因为您可以找到列表的头部和尾部,您可以这样做的任何 可折叠的 。

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

也就是说,尾部将有一个列表类型,而不是 可折叠的 (除非这是一个清单)。这归根结底是因为 可折叠的 可以实现UNCOS。例如:

data Pair a = Pair a a

这是 可折叠的 ,但你不能代表 Pair 使用A 一对 。

dfeuer 7 年前

要旋转,不需要任何难看的部分函数。这个奇怪的 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] .

dfeuer 7 年前

感谢所有回应的人!

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