可以查看最终结果的一部分的同构

Question

递归方案是否有一个名字，就像一个变形，但是可以在运行时查看最终结果？这是一个精心设计的示例：

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 fusion，中间体CappedList从未真正构建，并且toPercents在一次传递中消耗输入列表。正如 MoonGoose 所说，使用的要点CappedList是将求和放在（虚拟）中间结构的底部，以便正在完成的列表重建可以从一开始就访问它。percAlg

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