Схема рекурсии, допускающая зависимости между рекурсивными вызовами (упорядоченный катаморфизм?)

Меня интересует способ более высокого порядка (схема рекурсии) для написания рекурсивного кода, в котором могут быть зависимости между рекурсивными вызовами.

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

data Tree = Leaf Nat | Node Tree Tree

sumLT :: Nat -> Tree -> Bool
sumLT max t = sumLT' max t > 0

sumLT' :: Nat -> Tree -> Int
sumLT' max (Leaf n) = max - n
sumLT' max (Node l r) = 
  let max' = sumLT' max l
   in if max' > 0 then sumLT' max' r else 0

Есть ли способ выразить эту идею — по сути, упорядоченный обход — с помощью схемы рекурсии? Меня интересует как можно более общее составление упорядоченных обходов, подобных этому.

В идеале я хотел бы написать обходы, в которых функция, свернутая (или развернутая) над структурой данных, определяет порядок обхода. Какую бы абстракцию я ни получил, я хотел бы также написать версию обхода sumLT' в обратном порядке, где вместо этого мы идем справа налево:

sumLT'' :: Nat -> Tree -> Int
sumLT'' max (Leaf n) = max - n
sumLT'' max (Node l r) = 
  let max' = sumLT'' max r
   in if max' > 0 then sumLT'' max' l else 0

functional-programming fold haskell category-theory recursion-schemes
person trpnd    schedule 29.01.2021    source источник
comment
У вас нет дерева целых чисел, у вас есть дерево без значений. Поэтому sumLT' не будет компилироваться. Пожалуйста, убедитесь, что код вашего примера действительно компилируется, если только ваш вопрос не касается того, почему код не компилируется.   -  person amalloy    schedule 29.01.2021
comment
хороший улов спасибо   -  person trpnd    schedule 29.01.2021
comment
Ints может быть отрицательным. Вы хотели использовать Natural? Или предположить достаточно небольшое количество достаточно неотрицательных Int, чтобы они не переносились?   -  person dfeuer    schedule 29.01.2021
comment
Еще один хороший улов. Давайте сделаем их Nat и представим, что у нас есть средство доказательства теорем или что-то в этом роде. Пример (явно плохо продуманный) и вроде бы не относящийся к делу - я просто пытался придумать простой пример рекурсивного обхода, в котором есть зависимость между рекурсивными вызовами.   -  person trpnd    schedule 29.01.2021
comment
Я подозреваю, что вам лучше использовать что-то вроде Foldable или MFoldable для такого рода вещей, поскольку они выпекаются в понятии порядка. foldr, безусловно, справится с этой задачей.   -  person dfeuer    schedule 29.01.2021
comment
Что, если я не хочу жестко закодированного понятия порядка? Foldable - это единственный вариант, который у меня есть до сих пор - в основном любопытно, предоставляют ли схемы рекурсии (или что-то еще) более общие параметры. До сих пор я подозреваю, что не может быть ничего более общего, поскольку весь смысл схем рекурсии и тому подобного заключается в абстрагировании рекурсивной структуры, но мне любопытно, есть ли что-то более общее, скрывающееся за всей теорией категорий.   -  person trpnd    schedule 29.01.2021
comment
Не знаю, считается ли это схемой рекурсии, которую вы могли бы сделать any из scanl. scanl на самом деле не в Traversable, но в основном это особый случай mapAccumL, который есть. В общем, если вы хотите проверить промежуточные результаты, вы можете отработать сканирование.   -  person David Fletcher    schedule 29.01.2021
comment
Хм, кажется, scan все еще проходит в любом порядке, который определяет экземпляр Foldable, не так ли? В идеале я бы хотел, чтобы сама алгебра (функция складывалась) каким-то образом определяла порядок обхода   -  person trpnd    schedule 29.01.2021

Ответы (2)


arrow_upward
3
arrow_downward

Как обычно, свертывание в эндофункции дает вам понятие порядка обработки/передачи состояния:

import Numeric.Natural

data Tree = Leaf Natural | Node Tree Tree

cata :: (Natural -> r) -> (r -> r -> r) -> Tree -> r
cata l n (Leaf a)     = l a
cata l n (Node lt rt) = n (cata l n lt) (cata l n rt)

sumLT :: Natural -> Tree -> Bool
sumLT max t = cata (\ a max -> max - a)     -- left-to-right
                   (\ l r max -> let max' = l max in
                        if max' > 0 then r max' else 0)
                   t max > 0

sumLT' :: Natural -> Tree -> Bool
sumLT' max t = cata (\ a max -> max - a)     -- right-to-left
                    (\ l r max -> let max' = r max in
                         if max' > 0 then l max' else 0)
                    t max > 0

Пробуем:

> sumLT 11 (Node (Leaf 10) (Leaf 0))
True

> sumLT 11 (Node (Leaf 10) (Leaf 1))
False

> sumLT 11 (Node (Leaf 10) (Leaf undefined))
*** Exception: Prelude.undefined

> sumLT 11 (Node (Leaf 11) (Leaf undefined))
False

> sumLT 11 (Node (Leaf 10) (Node (Leaf 1) (Leaf undefined)))
False

> sumLT' 11 (Node (Leaf undefined) (Leaf 11))
False

Как обычно, ленивость Haskell предусматривает возможность закоротить/выйти раньше. Как видно из примеров, если cata's второй аргумент, функция свертывания узла, не требует значения одного из своих аргументов, соответствующая ветвь на самом деле вообще не посещается.

person Will Ness    schedule 30.01.2021
comment
Прохладный! Я думаю, что это может быть именно то, что я хотел - мой реальный вариант использования немного сложнее, чем мой пример (который мог быть ошибкой с точки зрения получения полезных ответов), но я должен быть в состоянии использовать эту идею! - person trpnd; 31.01.2021

arrow_upward
0
arrow_downward

Я бы использовал лень Haskell в своих интересах. Превратите дерево в список (это катаморфизм), создайте частичные суммы и найдите первое, которое больше предела.

{-# language DeriveFoldable #-}

module ShortSum where
import Data.Foldable
  
data Tree a = Leaf a | Node (Tree a) (Tree a)
  deriving Foldable

type Nat   = Int
type TreeN = Tree Nat

sumLt :: Nat -> TreeN -> Bool
sumLt mx = any (> mx) . scanl1 (+) . toList
person Bartosz Milewski    schedule 30.01.2021