Описание тега recursion-schemes
Схемы рекурсии - это шаблоны многократного использования для выполнения рекурсивных вызовов. К ним относятся катаморфизмы и анаморфизмы. Этот тег охватывает как общую концепцию, так и одноименную библиотеку Haskell.
1
ответ
Программирование схемы, прохождение списка и создание всего внутри списка
Домашнее задание: (diginlist '(4 5 3 2 8)) должен вернуться (4(5(3)2)8) (define(removelast L) (if(null?(cdr L)) '() (cons(car L) removelast(cdr L)))) (define(last L) (if(null?(cdr L)) (car L) (last(cdr L)))) (define(diginlist L) (cond((null? L) '())…
09 апр '18 в 00:13
2
ответа
Эффективная реализация катаморфизма в Scala
Для типа данных, представляющего натуральные числа: sealed trait Nat case object Z extends Nat case class S(pred: Nat) extends Nat В Scala приведен простейший способ реализации соответствующего катаморфизма: def cata[A](z: A)(l: Nat)(f: A => A): …
30 янв '17 в 21:10
1
ответ
Проблема рекурсии при написании версии Lens.para с поддержкой "Pretext"
Я пытался построить замену Lens.para это обеспечивает линзовые контексты для функции para, когда она выполняет свою работу. Однако, я, кажется, где-то допустил ошибку в рекурсии. Согласно моему пониманию, Lens.para является функцией параморфизма зна…
18 июн '17 в 07:16
3
ответа
Есть ли что-то вроде cata, но где вы можете сопоставить внутреннюю структуру?
У меня есть этот язык АСТ data ExprF r = Const Int | Var String | Lambda String r | EList [r] | Apply r r deriving ( Show, Eq, Ord, Functor, Foldable ) И я хочу преобразовать его в строку toString = cata $ \case Const x -> show x Var x -> x EL…
23 авг '16 в 16:14
2
ответа
RamdaJS reduBy() в Haskell с использованием рекурсивных схем
У меня есть следующий код, используя recursion-schemes библиотека: {-# LANGUAGE LambdaCase #-} {-# LANGUAGE TypeFamilies #-} import Data.Functor.Foldable import Data.Maybe import qualified Data.Map as M reduceBy valueAlgebra keyFn = cata $ fooAlgebr…
09 фев '17 в 23:17
1
ответ
Haskell: маркировка AST с информацией о типах с использованием алгоритма W
У нас есть определение AST: data Term a = Lam String a | App a a | Var String deriving(Read,Show,Eq,Functor,Foldable,Traversable) И F-алгебра для вывода типа: type Wrapped m a = Enviroment -> m a type Result m = Wrapped (Type,Substitution) w :: (…
09 сен '17 в 20:43
2
ответа
Расширение выражения с использованием рекурсивных схем
У меня есть тип данных, представляющий арифметические выражения: data E = Add E E | Mul E E | Var String Я хочу написать функцию расширения, которая преобразует выражение в сумму произведений переменных (своего рода расширение фигурных скобок). Испо…
16 мар '17 в 03:33
1
ответ
Что должен делать препроморфизм Фоккинга?
Я смотрел на recursion-schemes библиотека, и я очень смущен тем, что prepro предполагается использовать для, или даже то, что он делает. Описание этого как "препроморфизм Фоккинга" не очень информативен, и подпись (prepro :: Corecursive t => (for…
24 ноя '17 в 01:32
2
ответа
Доказательство закона слияния для раскрытия
Я читал статью Джереми Гиббона о программировании оригами и застрял в упражнении 3.7, в котором читателю предлагается доказать закон слияния для раскрытия списка: unfoldL p f g . h = unfoldL p' f' g' если p . h = p' f . h = f' g . h = h . g' Функция…
13 авг '17 в 22:25
1
ответ
Факторинг из рекурсии в комплексе АСТ
Для стороннего проекта, над которым я работаю, мне в настоящее время приходится иметь дело с абстрактным синтаксическим деревом и преобразовывать его в соответствии с правилами (особенности не важны). Само AST нетривиально, то есть имеет подвыражени…
09 май '17 в 22:42
1
ответ
Каковы правила составления f-алгебр в катаморфизме
Вот несколько простых F-алгебр для списков. Они работают с cata функция из библиотеки рекурсивных схем. import Data.Functor.Foldable algFilterSmall :: ListF Int [Int] -> [Int] algFilterSmall Nil = [] algFilterSmall (Cons x xs) = if x >= 10 the…
17 фев '18 в 17:29
1
ответ
Не удалось разрешить экземпляр типа Haskell
Я пытаюсь создать Cofree структура по анаморфизму, согласно этому посту. Но компилятор жалуется на несоответствие типов: Expected type: Base (Cofree Term E) (E, Fix Term) Actual type: CofreeF Term E (E, Fix Term) Но в исходном коде recursion-schemes…
02 июл '18 в 02:09
1
ответ
Возникла проблема с расширением Data.Functor.Foldable
В этом вопросе используются понятия / импорт из http://hackage.haskell.org/package/recursion-schemes-4.0/docs/Data-Functor-Foldable.html Я пытаюсь расширить это, чтобы пронизать данную монаду через катаморфизм. Вот код, который я пытаюсь скомпилиров…
19 ноя '13 в 15:52
1
ответ
Схемы рекурсии с несколькими типами
Прямо сейчас у меня есть AST для выражения, которое полиморфно по типу рекурсии: data Expr a = Const Int | Add a a Это было невероятно полезно, позволяя мне использовать тип для простой рекурсии (Fix Expr) и еще один, когда мне нужно приложить допол…
28 июн '18 в 00:25
1
ответ
Развертывание непустых структур в списках
Я хочу написать Foldable.toList для непустого розового дерева, использующего анаморфизм, но кажется невозможным извлечь последний элемент: import Data.Functor.Foldable data RoseTree a = RoseNode a [RoseTree a] ana5 :: RoseTree a -> [a] ana5 = ana…
15 фев '17 в 04:32
1
ответ
Почему оценивается неиспользованная ценность, произведенная катаморфизмом?
Я ожидал, что следующий код будет запущен и завершится немедленно, потому что p фактически никогда не используется, но вместо этого он работает более 7 минут, а затем, по-видимому, уничтожается ОС. {-# LANGUAGE DeriveFunctor #-} import Control.Monad…
16 окт '16 в 21:39
3
ответа
Указание сигнатуры типа функции в предложении where
Следующая функция реализует старую старую функцию фильтрации из списков с помощью библиотеки рекурсивных схем. import Data.Functor.Foldable catafilter :: (a -> Bool) -> [a] -> [a] catafilter p = cata alg where -- alg :: ListF a [a] -> [a…
23 янв '18 в 11:02
2
ответа
Алгоритм W с использованием рекурсивных схем
Я хотел иметь возможность сформулировать алгоритм вывода типа Хиндли-Милнера, используя типы данных с фиксированной точкой и схемы рекурсии. Не обращая внимания на все детали, кроме реальных рекурсивных частей: w env term = case term of Lam n e ->…
08 сен '17 в 23:43
2
ответа
Корекурсивные фибоначчи с использованием рекурсивных схем
Существует элегантное определение списка чисел Фибоначчи: fibs :: [Integer] fibs = fib 1 1 where fib a b = a : fib b (a + b) Можно ли перевести на использование? recursion-schemes библиотека? Самое близкое, что я мог получить, это следующий код, кот…
10 мар '17 в 19:34
1
ответ
Как gpostpro "сбежать из монады"?
Я пытаюсь понять, как эта очень абстрактная рекурсивная функция из Haskell recursion-schemes пакет работает (или, действительно, что он делает!) - из этого файла: class Functor (Base t) => Corecursive t where [...] -- | A generalized postpromorph…
25 сен '16 в 09:49