haskell - 允许查看最终结果的一部分的变质

Question

是否有一个类似于 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]
-}

此示例使用 total在折叠的每一步，即使它的值直到最后才知道。 (显然，这依赖于懒惰的工作。)

Answer 1

尽管这不一定是您要寻找的，但我们可以使用 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是， as moonGoose puts it ，将总和放在(虚拟)中间结构的底部，以便使用 percAlg 完成列表重建可以从一开始就访问它。

(也许值得注意的是，即使它是一次性完成的，似乎很难从这个技巧中获得良好且恒定的内存使用，无论是我的版本还是你的版本。欢迎在这方面提出建议。 )