категорический троллинг

[thedeemon]

Как развернуть список на окамле.

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

Comments

[sassa-nf.livejournal.com]

{-# LANGUAGE TypeSynonymInstances
           , FlexibleInstances #-}

import Data.Functor

data Mu f = In {unIn :: f (Mu f)}
data Nu f = Out {unOut :: f (Nu f)}

data N x = Z | S x

data E x = L Int | R x

instance Functor N where
  fmap f Z = Z
  fmap f (S x) = S (f x)

instance Functor E where
  fmap f (L i) = L i
  fmap f (R x) = R (f x)

data L a x = N | C a x deriving (Show)
type List a = Mu (L a)

instance Functor (L a) where
  fmap f N = N
  fmap f (C a x) = C a $ f x

nil = In N
cons = (In .) . C

cata :: (Functor f) => (f c -> c) -> Mu f -> c
cata phi = phi . fmap (cata phi) . unIn

ana :: (Functor f) => (c -> f c) -> c -> Nu f
ana phi = Out . fmap (ana phi) . phi

addN x y = cata phi x where
  phi Z = y
  phi (S x) = succN x

zeroN = In Z
succN = In . S

toInt :: (Mu N) -> Int
toInt = cata phi where
  phi Z = 0
  phi (S x) = 1+x

rev = cata phi where
  phi N = nil
  phi (C a x) = cata psi x where
    psi N = cons a nil
    psi (C a x) = cons a x

instance (Show a) => Show (List a) where
  show = cata phi where
    phi N = ""
    phi (C a x) = (show a)++x

main = do
         print $ toInt $ addN (succN $ succN $ succN $ zeroN) (succN $ succN $ zeroN) -- 3 + 2 == 5
         print $ rev $ cons 'a' $ cons 'b' $ cons 'c' $ cons 'd' nil

[thedeemon.livejournal.com]

Ага, только там человек окамл просил.
А чем тут отличаются Mu и Nu? :)
Разворачивание через аппенд не так прикольно и, кажися, менее эффективно.
На скале такое получится забабахать?

[sassa-nf.livejournal.com]

а я вот только что хотел подредактировать:

{- most direct solution:

rev = cata phi where
  phi N = nil
  phi (C a x) = cata psi x where
    psi N = cons a nil
    psi (C a x) = cons a x
-}

rev xs = cata phi xs nil where -- this is more concise, but still requires building just as large intermediate structure
  phi N = id
  phi (C a x) = x . cons a

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

На скале..... надо попробовать.

Mu и Nu ничем не отличаются, ибо индукция и коиндукция в Хаскелле не отличаются. Вармо Вене начитался, оттуда это всё.

[sassa-nf.livejournal.com]

а, пардон, дык, отвечавший на форуме это ты и есть? тогда кому я объясняю?! :)

[thedeemon.livejournal.com]

Я. :)

[maxim.livejournal.com]

Гг :) клево получилось, да )

[nivanych.livejournal.com]

Саша просто хочет доказать, что маргинальный хацкель не хуже весёлого звонкого окамелё ;-)

[thedeemon.livejournal.com]

Конечно, хуже! Тут же Объектный язык Категорной абстрактной машыны! А у вас Иван Петрович Карри какой-то.

[nivanych.livejournal.com]

> Иван Петрович Карри

Хаскель Моисеевич Брукс Карри!
Ви таки хотите сказать, что вся эта еврейская наука про хитрые типы неприменима в расово верных современных условиях? ;-)

А серьёзно, если пытаться строго прописывать категорную семантику современного окамелё, то очень проще хацкеля не получится точно.
Вот для классического ML ничо так получается.

[iamjaph.livejournal.com]

Классический ML - это SML? А за счет чего получается "ничо так"?

[nivanych.livejournal.com]

Нннуу, я имел в виду просто полиморфную лямбду, если точнее...
Получается _только_ за счёт простоты языка.
Если пытаться чОтко описывать те же модули, просто уже не выйдет.
Так что, в общем-то, я тут неправ.

[gds.livejournal.com]

хорошо, но жестоко. Но справедливо!11

[kodt-rsdn.livejournal.com]

Но справедливо. Но мало!
Чтобы было не мало, надо было голую лямбду приделать, со всеми этими безумными комбинаторами.

Не помню, как там минимально делается (помню только, что Nil и False одинаково определяются), поэтому, грубо говоря, начать можно с такого

Nil = \f -> f False undefined undefined
Cons h t = \f -> True h t

null xs = xs (\isnotnull _ _ -> not isnotnull)
head xs = xs (\True h _ -> h)
tail xs = xs (\True _ t -> t)

[maxim.livejournal.com]

Такое?

I      = lambda x. x,
    K      = lambda x. lambda y. x,
    S      = lambda x. lambda y. lambda z. (x z (y z)),
    mega   = lambda x. (x x),
    OMEGA  = mega mega,
    TRUE   = lambda x. lambda y. x,
    NULL   = lambda L. L (lambda h. lambda t. FALSE),
    MINUS  = lambda a. lambda b. b PRED a,
    DIVMOD = lambda x. lambda y.
              let rec dm = lambda q. lambda x.
                if LE y x then
                  dm (SUCC q) (MINUS x y)
                else pair q x
              in dm ZERO x,
    DIV    = lambda x. lambda y. DIVMOD x y fst,
    MOD    = lambda x. lambda y. DIVMOD x y snd,
    PAIR   = lambda fst. lambda snd. lambda sel. sel fst snd,
    PLUSb  = lambda x. x SUCC,
    FALSE  = ZERO,
    ZERO   = lambda s. lambda z. z,
    ONE    = lambda s. lambda z. s(z),
    TWO    = lambda s. lambda z. s(s(z)),
    PLUS   = lambda x. lambda y. lambda s. lambda z. x s (y s z),
    TIMES  = lambda x. lambda y. x (PLUS y) ZERO,
    PP     = lambda n. PRED (PRED n),
    PRED   = lambda n. lambda f. lambda x. n (lambda g. lambda h.h (g f)) (lambda u.x) (lambda u.u),
    SUCC   = lambda n. lambda f. lambda x. n (lambda g. lambda h.h (g f)) (lambda u.x) (lambda u.u),
    ISZERO = lambda n. n (lambda x. ZERO) TRUE,
    IF     = lambda p. lambda a. lambda b. p a b,
    PRINT  = lambda n. n (lambda m. 'I'::m) '.',
    CONS   = lambda h. lambda t. lambda f. f h t,
    NIL    = lambda f. true,
    NULL   = lambda L. L (lambda h. lambda t. false),
    HD     = lambda L. L (lambda h. lambda t. h),
    TL     = lambda L. L (lambda h. lambda t. t), 
    Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g)),
    FIB    = lambda f. lambda n. IF (ISZERO (PRED n)) ONE IF (ISZERO (PP n)) ONE (PLUS (f(PRED n))(f(PP n))),
    THREE  = PLUS ONE TWO,
    FOUR   = MINUS (TIMES THREE TWO) (PLUS ONE ONE),
    EIGHT  = PLUS FOUR FOUR

[nivanych.livejournal.com]

Да, помню, как мы с gds про это разговаривали и про монадки.
Он мне показал, что в окамелё это всё тоже наатлично реализуется.
Тогда-то я и поменял своё отношение к окамелю (в лучшую сторону).

[triampurum.livejournal.com]

http://gallium.inria.fr/~xleroy/mpri/2-4/monads.2up.pdf

вдруг прикотится (с), если не вам, то читателям