允许查看最终结果部分的Catamorphism

Question

允许查看最终结果部分的Catamorphism

haskelllazy-evaluationrecursion-schemescatamorphism

5

有没有一种递归方案的名称，类似于catamorphism，但允许在它仍在运行时查看最终结果？以下是一个稍微牵强的例子：

toPercents :: Floating a => [a] -> [a]
toPercents xs = result
  where
  (total, result) = foldr go (0, []) xs
  go x ~(t, r) = (x + t, 100*x/total:r)

{-
>>> toPercents [1,2,3]
[16.666666666666668,33.333333333333336,50.0]
-}

这个示例在fold的每个步骤中使用total，即使它的值直到最后才知道。(显然，这取决于惰性才能工作。)

- Joseph Sible-Reinstate Monica

这是组合子中的一种吧？我很确定这是foo-morphism之一；https://dev59.com/PloU5IYBdhLWcg3w_apJ 可以帮助你。 - chepner

@chepner 看起来不像是一个组织形态。特别是，它看起来像是一个组织形态只能访问“前面”的中间结果。 - Joseph Sible-Reinstate Monica

这不是未来主义吗？ - moonGoose

1

@moonGoose，futumorphism似乎是anamorphism的一种变体，它允许你设置未来。这是catamorphism的一个变体，可以让你查看它。 - Joseph Sible-Reinstate Monica

@JosephSible，这不是给出的解释，例如 https://jtobin.io/time-traveling-recursion，它将其描述为查看未来值的一种方式？ - moonGoose

1

@moonGoose 这段散文可能存在歧义，但我再读一遍，发现 futumorphism 取一个 coalgebra，这使它无疑是 anamorphism 的一种变体。 - Joseph Sible-Reinstate Monica

3个回答

2

我认为并没有明确的方案允许函数1在每一步中查看函数2的最终结果。虽然这似乎是一个有点奇怪的要求。最终，这将归结为以下两种方式之一：1）运行函数2，然后使用已知的函数2结果运行函数1（即两次通过，在您的示例中这是唯一获得常量内存的方法），或者2）并行运行它们，在最后创建一个函数thunk（或依赖于惰性）来合并它们。

当然，你给出的惰性foldr版本自然地转换成了一个catamorphism。下面是功能化的catamorphism版本。

{-# LANGUAGE LambdaCase #-}

import Data.Functor.Foldable    

toPercents :: Floating a => [a] -> [a]
toPercents = uncurry ($) . cata alg
  where
    alg = \case
        Nil -> (const [], 0)
        Cons x (f,s) ->  (\t -> 100*x / t : f t, s + x)

这段文字的翻译如下：

从风格上讲，手动并行两个catamorphism似乎不太好，特别是因为它不能编码一个渐进地不依赖于另一个的事实。Hoogle找到了bicotraverse，但它过于通用，所以让我们编写我们自己的代数并行化运算符(&&&&)。

import Control.Arrow

(&&&&) :: Functor f => (f a -> c) -> (f b -> d) -> f (a,b) -> (c,d)
f1 &&&& f2 = (f1 . fmap fst &&& f2 . fmap snd)

toPercents' :: Floating a => [a] -> [a]
toPercents' = uncurry ($) . cata (algList &&&& algSum)

algSum :: (Num a) => ListF a a -> a
algSum = \case
    Nil -> fromInteger 0
    Cons x !s -> s + x

algList :: (Fractional a) => ListF a (a -> [a]) -> (a -> [a])   
algList = \case
    Nil -> const []
    Cons x s -> (\t -> 100*x / t : s t)

- moonGoose

0

只是一次疯狂的实验。我认为我们可以融合一些东西。

此外，fix = hylo (\(Cons f a) -> f a) (join Cons)，我们可以在fix上进行替换。

toPercents :: Floating a => [a] -> [a]
toPercents xs = result
  where
    (_, result) = hylo (\(Cons f a) -> f a) (join Cons) $ \(~(total, _)) -> 
      let
        alg Nil = (0, [])
        alg (Cons x (a, as)) = (x + a, 100 * x / total: as)
      in
        cata alg xs

- xgrommx

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- duplode · Accepted Answer

虽然这可能不是您正在寻找的内容，但我们可以使用一种 hylomorphism 技巧来编码懒惰计算：

{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TemplateHaskell #-}

import Data.Functor.Foldable
import Data.Functor.Foldable.TH

data CappedList c a = Cap c | CCons a (CappedList c a)
    deriving (Eq, Show, Ord, Functor, Foldable, Traversable)
makeBaseFunctor ''CappedList

-- The seq here has no counterpart in the implementation in the question.
-- It improves performance quite noticeably. Other seqs might be added for
-- some of the other "s", as well as for the percentage; the returns, however,
-- are diminishing.
toPercents :: Floating a => [a] -> [a]
toPercents = snd . hylo percAlg sumCal . (0,)
    where
    sumCal = \case
        (s, []) -> CapF s
        (s, a : as) -> s `seq` CConsF a (s + a, as)
    percAlg = \case
        CapF s -> (s, [])
        CConsF a (s, as) -> (s, (a * 100 / s) : as)

这对应于惰性技巧，因为由于hylo融合的作用，中间的CappedList实际上从未被构建，而toPercents在单次遍历中消耗了输入列表。使用CappedList的重点是，正如moonGoose所说的那样，将总和放置在（虚拟）中间结构的底部，以便使用percAlg进行列表重建时可以从一开始就访问它。

（值得注意的是，尽管是单次遍历，但似乎很难从这个技巧中得到良好的、恒定的内存使用，无论是我的版本还是你的版本。欢迎提出关于此方面的建议。）