6

是否有一个递归方案的名称，它类似于 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在折叠的每一步都使用，即使它的值直到最后才知道。（显然，这依赖于懒惰的工作。）

4

3 回答 3

3

尽管这不一定是您要寻找的，但我们可以使用 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

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

于 2019-05-14T01:14:45.977 回答
2

我认为没有明确的方案允许函数 1 在函数 2 的最终结果中查看每一步。不过，这似乎有点奇怪。我认为最后，它会归结为 1) 运行函数 2，然后运行函数 1 并使用函数 2 的已知结果（即两次传递，我认为这是在你的内存中获得恒定内存的唯一方法例如）或2）并排运行它们，创建一个函数thunk（或依赖懒惰）在最后组合它们。

您提供的惰性foldr版本当然会自然地转化为变态。这是功能化的变质版本，

{-# 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)

但是，不得不手动并行化这两个变质在风格上似乎并不好，特别是因为它没有编码这样一个事实，即两者都没有逐步依赖于另一个。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)
于 2019-05-15T17:54:06.470 回答
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
于 2019-05-14T08:02:41.267 回答