Написать Functor

@al_chi · Регистрация: 13.01.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте. Недавно начал учить haskell, читаю книгу Изучаем Haskell (Beginning Haskell. A Project-Based Approach)
Но никак не могу понять как сделать упражнение 4.8

Дано дерево и несколько функций

Haskell
1
2
3
4
5
6
data BinaryTree a = Node a (BinaryTree a) (BinaryTree a)
                  | Leaf
 
treeFind :: Ord a => a -> BinaryTree a -> Maybe a
treeInsert :: Ord a => a -> BinaryTree a -> BinaryTree a
treeMerge :: Ord a => BinaryTree a -> BinaryTree a -> BinaryTree a

Надо написать Functor
Я написал так

Haskell
1
2
3
instance Functor BinaryTree where
    fmap f Leaf = Leaf
    fmap f (Node v l r) = treeInsert (f v) $ treeMerge (fmap f l) (fmap f r)

Но это не компилится, так как тип v должен принадлежать классу Ord.
Как правильно написать Functor для BinaryTree?

@Catstail · 13.01.2015, 16:43

Мне кажется, что так:

Haskell
1
2
3
instance Functor BinaryTree where
    fmap f Leaf = Leaf
    fmap f (Node v l r) = Node (f x) (fmap f l) (fmap f r)

@al_chi · 13.01.2015, 17:10 **[ТС]**

Забыл написать. Дерево упорядоченное

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

и должно таким остаться после применения fmap, поэтому реализация должна быть через treeInsert, treeMerge

Моя проблема в том, что в определении типа BinaryTree на a не наложено ограничение, что a может быть только экземпляром класса Ord, а в функциях это ограничение есть. Поэтому при реализации fmap я не могу использовать функции treeInsert и treeMerge, компилятор ругается что нет инстанца Ord.

@Araneo · 13.01.2015, 17:54

дайте код функций типы к которым описаны и я поправлю

)

Добавлено через 7 минут
а не не могу... раньше это можно было решить расширением DatatypeContexts ... но его видите ли выпилили...
определение типа выглядело бы так...

Haskell
1
2
data Ord a => BinaryTree a = Node a (BinaryTree a) (BinaryTree a)
                  | Leaf

сейчас даже не знаю.

@al_chi · 13.01.2015, 18:03 **[ТС]**

При этом на следующей же странице в книге написано

Следует заметить, что класс Set не может быть экземпляром Functor. Причина в том, что функция обхода (типа map) для множеств имеет тип Ord b => (a -> b) -> Set a -> Set b, который не-совместим с типом Functor, не имеющим никаких ограничений. В настоящее время язык Haskell предоставляет достаточное количество инструментов для создания другого класса типов для функторов, допускающего присутствие класса Set внутри себя. Но это усложнит механизм ис-пользования класса типов Functor и приведет в негодность большие объемы уже существующего кода .Поэтому в библиотеки включается простая версия Functor.

-_-

Пытался найти готовые решения к книге, не нашел.

@Mysterious Light · 13.01.2015, 19:24

al_chi, я предлагаю исходить не из поставленной задачи, как это бывает в темах «Помогите решить, дано неведомо-что, что это значит не знаем, но преподаватель требует и не объясняет», а из смысла, который мы хотим вложить.

Рассмотрим BinaryTree. Этот тип данных рекурсивный, основанный на полиномиальном функторе , что означает примерно то, что Ваше определение BinaryTree может быть переписано с

Haskell
1
2
data BinaryTreeStructure a x = Leaf | Node x a x
data BinaryTree a = BinaryTreeStructure a (BinaryTree a)

Такие структуры являются функторами, их частный случай — свободные функторы (которые к тому же являются монадами), см. пост Catstail.

Вы же хотите определить fmap' :: (Ord a, Ord b) => (a -> b) -> BinaryTree a -> BinaryTree b именно с такой сигнатурой. Это не Functor, но это может рассматриваться как функтором, а именно функтор из категории всех Ord в категорию всех BinaryTree.

Не по теме:

многабукоф

Дело в том, что Functor определяет fmap :: (a -> b) -> BinaryTree a -> BinaryTree b, что по сути является функтором из категории типов Hask в подкатегорию Hask всех типов BinaryTree. Точнее, это может рассматриваться либо как функтор из Hask в BinaryTree, либо (и это более привычно) как функтор из Hask в Hask, когда область значения функтора инъективно погружается в Hask тривиальным образом.
Ваша функция имеет сигнатуру fmap' :: (Ord a, Ord b) => (a -> b) -> BinaryTree a -> BinaryTree b и выражает как бы функтор из подкатегории Hask всех Ord в подкатегорию Hask всех BinaryTree:

Haskell
1
2
3
4
5
6
7
8
class OrdFunction f where
  fmap' :: (Ord a, Ord b) => (a -> b) -> f a -> f b
 
instance OrdFunction BinaryTree where
  fmap' = ...
 
instace Functor f => OrdFunctor f where
  fmap' = fmap

На досуге подумаю, можно ли это как-то красиво записать в терминах Category и Arrow.

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

@Curry · 13.01.2015, 20:52

Сообщение от Araneo

раньше это можно было решить расширением DatatypeContexts

Зато теперь

Haskell
1
2
3
4
5
{-# LANGUAGE DeriveFunctor #-}
 
data BinaryTree a = Node a (BinaryTree a) (BinaryTree a)
                  | Leaf
                  deriving Functor

Не по теме:

Изюм!!!! Булки!!!! :)

@Mysterious Light · 13.01.2015, 20:56

KolodeznyDiver, GHC реализует функтор на основании того, что тип порождёт полиномиальным функтором (см. пост выше), так, как написал наш коллега (см. 5 постов выше), и ТС такая имплементация не нравится, мол, как же упорядоченность. Araneo говорил о том, что раньше в определении типов данных с параметрами можно было накладывать ограничения на параметры, а сейчас такое выпилено из языка.

@Curry · 13.01.2015, 23:10

Сообщение от al_chi

Как правильно написать Functor для BinaryTree?

Нет однозначного правила, что должен делать функтор для конкретного типа. Однако, он должен удовлетворять законам функтора:

fmap id = id
fmap (g . h) = fmap g . fmap h

Для сортированного дерева функтор не получится - не пройдёт по второму закону.

Сообщение от Mysterious Light

свободные функторы (которые к тому же являются монадами), см. пост Catstail

??? Как из поста Catstail, где определяется экземпляр функтора, следует что функтор стал монадой?

Сообщение от Mysterious Light

Araneo говорил о том, что раньше в определении типов данных с параметрами можно было накладывать ограничения на параметры, а сейчас такое выпилено из языка.

Я читал пост Araneo, на который отвечал.

Добавлено через 6 минут
Думаю, не вредно будет посмотреть библиотечную реализацию дерева. Оно, несколько другое - вместо фиксированного кол-ва листьев , там они списком. И функторы дерева, и монады ...

@Mysterious Light · 13.01.2015, 23:33

Сообщение от KolodeznyDiver

??? Как из поста Catstail, где определяется экземпляр функтора, следует что функтор стал монадой?

Никак, как и все другие общезначимые истины. А сказал я не более, чем то, что подобный рекурсивный имеет естественную имплементацию Functor и Monad. Это не исключает возможности сделать и другие имплементации, как этого хочет ТС, но уж по меншей мере вариант Catstail тоже достоин внимания.

Сообщение от KolodeznyDiver

Думаю, не вредно будет посмотреть библиотечную реализацию дерева. Оно, несколько другое - вместо фиксированного кол-ва листьев , там они списком. И функторы дерева, и монады ...

Не вредно, но опять же — не то, что нужно ТС, и о чём вообще эта тема. Во-первых, листы списком — это не Binary Tree; во-вторых, там тоже про упорядочение ничего не говорится.

@Araneo · 14.01.2015, 05:11

попробовал через GADTs тоже облом... ладно буду думать дальше...

Новые блоги и статьи Все статьи Все блоги /
BOINC: 22 года — и всё ещё работает Programma_Boinc 12.03.2026 BOINC: 22 года — и всё ещё работает Дэвид Андерсон написал ретроспективу. Кратко: в 2001 году он ушёл из United Devices, где был CTO, и за несколько месяцев написал ядро BOINC — клиент, сервер,. . .	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@Mysterious Light $Эксперт по математике/физике$ 4313 / 2105 / 431 Регистрация: 19.07.2009 Сообщений: 3,204 Записей в блоге: 24
	13.01.2015, 20:56
	KolodeznyDiver, GHC реализует функтор на основании того, что тип порождёт полиномиальным функтором (см. пост выше), так, как написал наш коллега (см. 5 постов выше), и ТС такая имплементация не нравится, мол, как же упорядоченность. Araneo говорил о том, что раньше в определении типов данных с параметрами можно было накладывать ограничения на параметры, а сейчас такое выпилено из языка. 0

@Araneo 650 / 260 / 16 Регистрация: 02.03.2014 Сообщений: 587
	14.01.2015, 05:11
	попробовал через GADTs тоже облом... ладно буду думать дальше... 0