Как обновить структуру рекурсивными схемами? - PullRequest
Новая
       55

Как обновить структуру рекурсивными схемами?

6 голосов
/ 03 октября 2019

В схемах рекурсии, как я могу построить что-то с определением типа, например (Recursive t, CoRecursive t) -> t -> ? -> t

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

update :: [a] -> Natural -> a -> [a]
update = para palg where
  palg Nil _ _ = []
  palg (Cons a (u, _)) 0 b = b : u
  palg (Cons a (u, f)) n b = a : f (n-1) b

update' :: [a] -> Natural -> a -> [a]
update' = c2 (apo acoalg) where
  c2 f a b c = f (a,b,c)
  acoalg ([], _, _) = Nil
  acoalg (_:as , 0, b) = Cons b $ Left as
  acoalg (a:as , n, b) = Cons a $ Right (as, n-1, b)

Однако эти две реализации хороши. В этих двух реализациях конструктор ListF и [] появляется с обеих сторон уравнения. И определение не кажется уникальным. Есть ли лучший способ выполнить обновление списка со схемами рекурсии?

1 Ответ

1 голос
/ 19 октября 2019

Схемы рекурсии - гибкий подход. Вы также можете реализовать свой собственный вариант.

(Повторное использование cata) 

zipo :: (Recursive g, Recursive h) => (Base g (h -> c) -> Base h h -> c) -> g -> h -> c
zipo alg = cata zalg
 where
  zalg x = alg x <<< project

update :: forall a. [a] -> Natural -> a -> [a] 
update xs n a = zipo alg n xs 
  where
    alg :: Maybe ([a] -> [a]) -> ListF a [a] -> [a]
    alg _ Nil = []
    alg Nothing (Cons y ys) = a:ys
    alg (Just n') (Cons y ys) = y:(n' ys)

Также вы можете реализовать некоторую параллельную версию, такую ​​как 

zipCata :: (Recursive g, Recursive h) => ((g -> h -> r) -> Base g g -> Base h h -> r) -> g -> h -> r
zipCata phi x y = phi (zipCata phi) (project x) (project y)

update' :: forall a. [a] -> Natural -> a -> [a]    
update' xs n a = zipCata alg n xs 
  where
    alg :: (Natural -> [a] -> [a]) -> Maybe Natural -> ListF a [a] -> [a]
    alg _ _ Nil = []
    alg _ Nothing (Cons _ ys) = a:ys
    alg f (Just n) (Cons y ys) = y:(f n ys)

Оба варианта (такжекак ваш) получит такой же результат

PS. Ненавижу подход для примера кода на SO

...