RamdaJS reduceBy（）在Haskell使用递归的方案

我使用recursion-schemes库下面的代码：RamdaJS reduceBy（）在Haskell使用递归的方案

{-# LANGUAGE LambdaCase #-} 
{-# LANGUAGE TypeFamilies #-} 
import Data.Functor.Foldable 
import Data.Maybe 

import qualified Data.Map as M 

reduceBy valueAlgebra keyFn = cata $ fooAlgebra valueAlgebra keyFn 

fooAlgebra 
    :: Ord k => 
    (ListF t a -> a) -> (t -> k) -> ListF t (M.Map k a) -> M.Map k a 
fooAlgebra valueAlgebra keyFn = \case 
    Nil -> M.empty 
    Cons elt acc -> M.alter 
     (Just . (valueAlgebra . Cons elt) . fromMaybe (valueAlgebra Nil)) 
     (keyFn elt) 
     acc

用作let countBy = reduceBy (\case Nil -> 0 ; Cons a b -> succ b) id in countBy [42,5,5,8,8,8]。代码模仿http://ramdajs.com/docs/#reduceBy

有没有更好的方法来实现reduceBy使用recursion-schemes？ alter论据看起来很脆弱，而且cata真的很合适吗？我听说有些东西可以实现为ana和cata。

来源

2017-02-09 nponeccop

好像你可以使用catamorphism来获取列表的映射，然后只是'fmap'每个组的catamorphism（折叠，真的）。 – danidiaz

一个更模块化的方式来应用'valueAlgebra'？似乎是一个好主意。现在我将代数传递给'alter'，它接受它的教会编码版本。解码是痛苦的。 – nponeccop

我没有看到你的方法有什么问题。 alter的论点不太好看，但主要是使用alter有点笨拙。既然你不需要从地图上删除元素，可以使用insertWith而不是alter改写fooAlgebra ...

fooAlgebra 
    :: Ord k => 
    (ListF t a -> a) -> (t -> k) -> ListF t (M.Map k a) -> M.Map k a 
fooAlgebra valueAlgebra keyFn = \case 
    Nil -> M.empty 
    Cons elt acc -> M.insertWith 
     (\_ grpAcc -> valueAlgebra (Cons elt grpAcc)) 
     (keyFn elt) 
     (valueAlgebra (Cons elt (valueAlgebra Nil))) 
     acc

...您可能会或可能不会找到一个改进。

至于使用变形，感觉就像是一件很自然的事情，因为你正在破坏原始结构以产生元素的组合概要。（同样值得注意的是，如果keyFn是一个常量函数，那么reduceBy本质上就是所有元素的普通旧折叠，其中valueAlgebra）。丹尼迪亚兹所暗示的重构（即将变形与分组之间的区分）可以证明更加明显：

reduceBy valueAlgebra keyFn = 
    fmap (cata valueAlgebra) . cata (groupAlgebra keyFn) 

groupAlgebra 
    :: Ord k => (t -> k) -> ListF t (M.Map k [t]) -> M.Map k [t] 
groupAlgebra keyFn = \case 
    Nil -> M.empty 
    Cons elt acc -> M.alter 
     (Just . (elt :) . fromMaybe []) 
     (keyFn elt) 
     acc

来源

2017-02-10 18:50:17 duplode

我自己基于所有的意见，到目前为止尝试：

type ListAlgebra a b = ListF a b -> b 

reduceBy :: Ord k => ListAlgebra t b -> (t -> k) -> [t] -> M.Map k b 
reduceBy valueAlgebra keyFn x = cata valueAlgebra <$> cata groupAlgebra x where 
    groupAlgebra = \case 
     Nil -> M.empty 
     Cons elt acc -> M.alter (Just . maybe [elt] (elt:)) (keyFn elt) acc

攻击的另一个方向是要注意到，keyFn可以分解出groupAlgebra的，因此它成为groupAlgebra' :: ListAlgebra (k, v) (M.Map k [v])。在这种形式，它正是一个embed，尽管有些奇特：

newtype XMap k v = XMap { unXMap :: M.Map k [v] } 
type instance Base (XMap k v) = ListF (k, v) 
instance Ord k => Corecursive (XMap k v) where 
    embed = \case 
     Nil -> XMap M.empty 
     Cons (key,elt) acc -> XMap $ M.alter (Just . maybe [elt] (elt:)) key $ unXMap acc

没有固定点创建该实例的过程中受到伤害。

reduceBy :: Ord k => ListAlgebra t b -> (t -> k) -> [t] -> M.Map k b 
reduceBy valueAlgebra keyFn = 
    fmap (cata valueAlgebra) . unXMap . refix . map (keyFn &&& id)

注意，这种方法是完全模块化：我们reduceBy现在可以用refix“演员”（一hylomorphism即获得其代数和余代数从(Co)recursive实例）来构建你可以轻松地撕裂功能分割成独立并且还可以使用变形和其他展开而不是仅仅消费列表来灵活地构建地图。

来源

2017-02-11 00:21:39 nponeccop

RamdaJS reduceBy（）在Haskell使用递归的方案

回答

相关问题