Описание тега catamorphism

Описание тега Вопросы с тегом
Используйте катаморфизм в вопросах, чтобы ссылаться на функции, которые рекурсивно перебирают структуру данных, чтобы вернуть новую структуру. Новая структура является производной от процесса применения одной или нескольких функций к данным на каждой итерации вместе с результатом предыдущих итераций.
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
3 ответа

Каковы практические примеры функций высшего порядка foldl и foldr?

Типичным академическим примером является подведение списка. Существуют ли реальные примеры использования сгиба, которые проливают свет на его полезность?
04 май '12 в 05:45
1 ответ

Катаморфизм в F#

Я читаю статью в Википедии о катаморфизмах, и на данный момент я смог воспроизвести примеры на Haskell на F#, за исключением этой части: type Algebra f a = f a -> a -- the generic f-algebras newtype Fix f = Iso { invIso :: f (Fix f) } -- gives us…
12 сен '17 в 09:43
2 ответа

Как сложить n-арное дерево в C#

Я хотел бы сделать сгиб по n-арным структурам данных Tree. (сложный агрегат в Линке)Мне удалось придумать рабочее решение: public static R Aggregate<T, R>(T node, Func<T, IEnumerable<T>> getChildren, Func<T, IEnumerable<R>…
23 окт '13 в 14:04
4 ответа

Когда состав катаморфизмов является катаморфизмом?

Со страницы 3 http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pdf: в общем случае неверно, что катаморфизмы замкнуты по составу При каких условиях катаморфизм превращается в катаморфизм? Более конкретно (при условии, что я …
24 авг '12 в 04:50
3 ответа

Как бы я реализовал эту функцию сгиба?

Даны два типа данных: Цвет и Растение. data Color = Red | Pink | White | Blue | Purple | Green | Yellow deriving (Show, Eq) data Plant = Leaf | Blossom Color | Stalk Plant Plant deriving (Show, Eq) Теперь я должен реализовать функцию fold_plant след…
04 июл '17 в 22:12
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 ответа

Реализация катаморфизма для недвоичных деревьев в сравнении с композитным шаблоном проектирования

На данный момент мечта все еще продолжается, в каждой концепции Haskell я узнаю, что я более заманчивый. И все же я не полностью выполнил работу над ответом этого драгоценного @ luqui на мой предыдущий вопрос о катаморфизме, и я вернусь к нему, пока…
20 янв '11 в 00:33
1 ответ

F#: Катаморфизмы для взаимно рекурсивных структур данных

Предположим следующую взаимно рекурсивную структуру: type Tree<'a> = | Empty | Node of 'a * 'a Forest and Forest<'a> = | Nil | Cons of 'a Tree * 'a Forest Цель: создать общие катаморфизмы для этой структуры: foldl, foldr, foldk. Я породи…
26 окт '16 в 05:54
2 ответа

Ана-/ Катаморфизмы только медленнее?

После написания этой статьи я решил положить свои деньги туда, где я живу, и начал преобразовывать мой предыдущий проект в использование. recursion-schemes, Структура данных, о которой идет речь, является ленивым kdtree. Пожалуйста, взгляните на реа…
14 май '14 в 20:09
2 ответа

Как заставить катаморфизмы работать с параметризованными / индексированными типами?

Недавно я немного узнал о F-алгебрах: https://www.fpcomplete.com/user/bartosz/understanding-algebras. Я хотел поднять эту функциональность до более продвинутых типов (индексированных и более привязанных). Кроме того, я проверил "Предоставление Haske…
06 июл '13 в 12:48
1 ответ

Схемы рекурсии в Агде

Излишне говорить, что стандартная конструкция в Haskell newtype Fix f = Fix { getFix :: f (Fix f) } cata :: (Functor f) => (f a -> a) -> Fix f -> a cata f = f . fmap (cata f) . getFix это здорово и очень полезно. Попытка определить похож…
05 фев '13 в 02:43
0 ответов

Как смешать CoFree в катаморфизме F-алгебры?

Во-первых, он основан на https://www.schoolofhaskell.com/user/bartosz/understanding-algebras поэтому, пожалуйста, ознакомьтесь с контекстом, если вы не знакомы с алгебрами и схемами рекурсии. Скажем, у меня есть простой анализатор выражений: data Ex…
22 окт '16 в 14:14
1 ответ

Как работать с AST с аннотацией Cofree?

У меня есть это просто Expr АСТ, и я могу легко преобразовать его в String, import Prelude hiding (Foldable) import qualified Prelude import Data.Foldable as F import Data.Functor.Foldable import Data.Monoid import Control.Comonad.Cofree data ExprF …
19 июл '16 в 15:20
1 ответ

Катаморфизмы для церковных списков

Я хочу быть в состоянии использовать cata от recursion-schemes пакет для списков в церковной кодировке. type ListC a = forall b. (a -> b -> b) -> b -> b Я использовал второй тип ранга для удобства, но мне все равно. Не стесняйтесь добавл…
16 июл '15 в 21:38
1 ответ

Есть ли у каждого типа уникальный катаморфизм?

Недавно я наконец начал чувствовать, что понимаю катаморфизмы. Я написал кое-что о них в недавнем ответе, но вкратце я бы сказал, что катаморфизм для абстракций типов в процессе рекурсивного обхода значения этого типа с сопоставлением с образцом это…
04 окт '17 в 09:11
2 ответа

Каково соотношение сгибов на Option, Either и т. Д. И сгиб на Traversable?

Скалаз предоставляет метод с именем fold для различных ADT, таких как Boolean, Option[_], Validation[_, _], Either[_, _] и т. д. Этот метод в основном принимает функции, соответствующие всем возможным случаям для данного ADT. Другими словами, образе…
16 дек '11 в 20:48
1 ответ

Каким образом у Scala Option складывается катаморфизм?

Ответ на этот вопрос предполагает, что метод сгиба на Option в Scala является катаморфизмом. Из википедии катамофизм - это "уникальный гомоморфизм из начальной алгебры в некоторую другую алгебру. Эта концепция была применена к функциональному програ…
18 май '14 в 16:27
1 ответ

Можно ли заставить GHC оптимизировать (вырубать) общие функции, такие как катаморфизмы?

Мне действительно нравится идея работы с катаморфизмами / анаморфизмами в общем виде, но мне кажется, что у нее есть существенный недостаток производительности: Предположим, что мы хотим работать с древовидной структурой категорическим образом - опи…
27 окт '12 в 10:12
0 ответов

Как переписать Single(OrDefault) с помощью LINQ Aggregate Catamorpshim?

Я читал статью, написанную Бартом де Сметом довольно давно: http://community.bartdesmet.net/blogs/bart/archive/2009/11/08/jumping-the-trampoline-in-c-stack-friendly-recursion.aspx Читателю оставлено в качестве упражнения определение всех других ката…
12 фев '17 в 14:19