我有以下代码使用recursion-schemes
库:
{-# 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
有没有更好的方法来使用 recursion-schemes
实现reduceBy
?alter
论点似乎很脆弱,cata
真的合适吗?我听说有些东西既可以ana
也可以实现cata
.
我自己的尝试基于到目前为止的所有建议:
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
可以用refix
"cast"(一种从(Co)recursive
实例中获取代数和代数的同态(来构造:
reduceBy :: Ord k => ListAlgebra t b -> (t -> k) -> [t] -> M.Map k b
reduceBy valueAlgebra keyFn =
fmap (cata valueAlgebra) . unXMap . refix . map (keyFn &&& id)
请注意,该方法是完全模块化的:您可以轻松地将函数分解为独立的组合器,并且还可以使用变形和其他展开灵活地构建映射,而不仅仅是使用列表。
我认为你的方法没有任何问题。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
。danidiaz建议的重构(即将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