Определение монады с нуля в Haskell

Question

После изучения монад в Haskell - предмета, который очень привлекателен для всего, что подразумевается, - интересно, смогу ли я определить монаду самостоятельно, не используя уже определенные типы классов.

Вместо того, чтобы Monad Экземпляр Functor, я просто хочу, чтобы определить монады само по себе, с его собственной fmap функции (Кроме того, я хотел бы изменить некоторые имена функций, таких как return и называют его unit).

Монады может быть определен оператором (>>=) связывания и функциями return, но она также может быть определен в терминах return и join с этого последней функции он может быть выражен в терминах оператора связывания: join m = m >>= id. Таким образом, монада может быть (технически) определена в терминах return и join и ничего больше. Требуется функция fmap (и основание существования Functor в Haskell), но также может быть определена в терминах return, так как она может быть определена также (я думаю) следующим образом: fmap f m = m >>= return . f(перед редактированием было написано, fmap f m = return . f, это была опечатка).

Но я знаю, что это будет не так эффективно, как использовать предопределенный класс Monad, это просто лучше понять язык Haskell.

Как это сделать? Это описание этой концепции из моей головы, прямо сейчас, так что это не полезно код:

-- Just a sketch 
infixr 9 ∘ 
(∘) :: (b -> c) -> (a -> b) -> a -> c 
(∘) g f x = g (f x) 
--(f ∘ g) x = f (g x) 

-- My own 'fmap' 
--mapper id = id 
--mapper (f ∘ g) = mapper f ∘ mapper g 


-- My monad 
class MyMonadBase (m :: * -> *) where 
    unit :: a -> m a --return 

    join :: m (m a) -> m a 
    join = (>>= id) 

    mapper f m = m >>= unit ∘ f 


--Testing: 
data Tree a = Leaf a | Branch (Tree a) (Tree a) 

instance MyMonadBase Tree where 
    unit = Leaf 
    join (Leaf x) = x 
    join (Branch l r) = Branch (join l) (join r) 

ли я в правильном направлении (концептуально)?

Answer 1

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

-- My monad 
class MyMonad m where 
    unit :: a -> m a 
    join :: m (m a) -> m a 
    mapf :: (a -> b) -> m a -> m b 


--Testing MyMonad 
data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show) 

instance MyMonad Tree where 
    unit = Leaf 
    join (Leaf x) = x 
    join (Branch l r) = Branch (join l) (join r) 
    mapf f (Leaf x) = Leaf (f x) 
    mapf f (Branch l r) = Branch (mapf f l) (mapf f r) 

t = Branch (Branch (Leaf 1) (Leaf 3)) (Branch (Leaf 2) (Leaf 4)) 


-- My bind (just for completeness, not that I need it for this example) 
(>>>) :: MyMonad m => m a -> (a -> m b) -> m b 
xs >>> f = join (mapf f xs) 


-- Testing my bind 
extr :: Integer -> Tree Integer 
extr x = Branch (Leaf (x^2)) (Leaf (2^x)) 

t >>> extr 
--Branch (Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 9) (Leaf 8))) 
--  (Branch (Branch (Leaf 4) (Leaf 4)) (Branch (Leaf 16) (Leaf 16))) 

Answer 2

Некоторые небольшие поправки:

Монада может быть определена оператором (>>=) связывания и функции return, но она также может быть определена в терминах return и join с этого последнего функция может быть выражена условия оператора привязки: join m = m >>= id.

Вывод («[монада] также могут быть определены в терминах return и join„) является правильным, но помещение (“так как [join] могут быть выражены в терминах оператора связывания») делает не подразумевайте это. Вместо этого вы должны показать, что оператор, которого вы опускаете - оператор привязки, может быть определен с точки зрения вещей, которые у вас есть - return и join. После того, как вы попытаетесь сделать это, вы понимаете, почему это так важно, что монада также функтор:

m >>= f = join (fmap f m) 

Функция fmap требуется (и основа существования Functor в Haskell), но также могут быть определены в терминах return, ибо оно может быть определено также (я думаю) следующим образом: fmap f m = return . f

это не совсем правильное определение fmap - и вы должны быть подозрительными на самом деле, так как правая рука сторона не упоминает m!Правильная версия будет:

fmap f m = m >>= return . f 

Но теперь это круговое определение, так как выше мы планировали по определению (>>=) с точки зрения fmap. Поэтому, если вы хотите сделать return и join основными операциями Monad, вам действительно нужно реализовать fmap отдельно.

Я знаю, что это не будет столь же эффективным, как с использованием предопределенного Monad класса типов

Я не вижу никаких оснований полагать, что это априори. Причина (>>=) выбрана над join не потому, что она более эффективна, а потому, что это такая естественная операция при использовании монадов в программировании.

Что касается вашего реального кода, я думаю, это выглядит хорошо с двумя оговорками:

1. Я сильно подозреваю, что ваше определение mapper не делать то, что вы думаете, что он делает. В строке mapper id = id рисунок id с левой стороны соответствует всем входящим значениям, а переменная id с правой стороны возвращает их без изменений. Строка mapper (f ∘ g) = mapper f ∘ mapper g просто недействительна Haskell. (Возможно, эти две линии были предназначены для документирования законов, требуемых mapper, а не фактический код?)

2. Странно предложить реализацию по умолчанию join и mapper с точки зрения (>>=) - как по указанным выше причинам (все три являются фундаментальными и должны быть определены) и потому, что (>>=) не является операцией класса, поэтому не может быть определен пользователем значимым образом.