RamdaJS ReduceBy() в Haskell, используя рекуррентную-схему

Question

У меня есть следующий код, используя 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

Есть ли лучший способ реализовать reduceBy с помощью recursion-schemes? Аргументы alter кажутся хрупкими и cata действительно уместны? Я слышал, что некоторые вещи реализуются как ana, так и cata.

Answer 1

Я не вижу ничего плохого в вашем подходе. Аргументы для alter не слишком приятны для просмотра, но в основном это сигналы alter немного неуклюжи в использовании. Так как вам не нужно, чтобы удалить элементы из карты, можно переписать fooAlgebra используя insertWith вместо alter ...

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.) Рефакторинг, который предлагает данидиаз (т.е. разделение катаморфизма 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 

Answer 2

Моя собственная попытка на основе всех советов до сих пор:

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 «литой» (в гилеморфизм, который получает алгебру и коалгебру из (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) 

Следует отметить, что подход является полностью модульным: вы можете легко оторвать функцию друг от друга на независимые Комбинаторы, а также могут гибко строить карты, используя анаморфизмы и другие разворачивания вместо того, чтобы просто потреблять списки.