可以查看最终结果的一部分的同构 [英] Catamorphism that allows looking at part of the final result

问题描述

是否有一个递归方案的名称，就像一个变态法，但是它允许在仍运行时查看最终结果?这是一个精心设计的示例:

Is there a name for a recursion scheme that's like a catamorphism, but that allows peeking at the final result while it's still running? Here's a slighly contrived example:

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 ，即使直到结束时才知道其值.(显然，这取决于工作的懒惰.)

This example uses total at each step of the fold, even though its value isn't known until the end. (Obviously, this relies on laziness to work.)

推荐答案

虽然这不一定是您所需要的，但我们可以使用同胚性来编码懒惰技巧:

Though this is not necessarily what you were looking for, we can encode the laziness trick with a 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 的重点是

This corresponds to the laziness trick because, thanks to hylo fusion, the intermediate CappedList never actually gets built, and toPercents consumes the input list in a single pass. The point of using CappedList is, as moonGoose puts it, placing the sum at the bottom of the (virtual) intermediate structure, so that the list rebuilding being done with percAlg can have access to it from the start.

(也许值得一提的是，即使它是一次性完成的，但无论是我的版本还是您的版本，似乎都很难从此技巧中获得良好而稳定的内存使用.欢迎.)

(It is perhaps worth noting that, even though it is done in a single pass, it seems difficult to get nice-and-constant memory usage from this trick, be it with my version or with yours. Suggestions on this front are welcome.)

这篇关于可以查看最终结果的一部分的同构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！