gpt4 book ai didi

haskell - Haskell 中的 RamdaJS reduceBy() 使用递归方案

转载 作者:行者123 更新时间:2023-12-02 12:17:38 25 4
gpt4 key购买 nike

我有使用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来实现reduceByalter 参数似乎很脆弱,cata 真的适合吗?我听说有些东西可以作为 anacata 实现。

最佳答案

根据迄今为止的所有建议,我自己的尝试:

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])。在这种形式下,它确实是一个嵌入,尽管有些奇怪:

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)

请注意,该方法是完全模块化的:您可以轻松地将函数分解为独立的组合器,并且还可以使用变形和其他展开来灵活地构造映射,而不仅仅是使用列表。

关于haskell - Haskell 中的 RamdaJS reduceBy() 使用递归方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42148749/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com