Бананы, линзы...

[lomeo]

Прочёл этот великолепный труд, который мне советовал polter.
По крайней мере понял откуда растут ноги у fold/unfold для произвольного типа. Я это и раньше чувствовал, но теперь получил формализованный вариант :-)


Параморфизм относительно легко рисуется на Haskell. Нам надо всего лишь определить для конкретного типа две
функции:

• определения, является ли значение стартовым (в силу того, что параморфизм работает над типами данных, обладающих... э-э-э.. индуктивной природой)


• разложения конструктора типа данных на пару составных частей

class Para a b | a -> b where
    start :: a
    decompose :: a -> (b, a)
--
instance Para Int Int where
    start = 0
    decompose (n+1) = (n,n)
--
instance Para [a] a where
    start = []
    decompose (x:xs) = (x,xs)
--
-- Сама функция
--
para f b x
    | x == start = b
    | otherwise  = f m (para f b n)
    where
        (m,n) = decompose x

Теперь легко определить функции, являющиеся параморфными:

paraFac  = para (\n m -> (n+1)*m) 1
paraTails = para (\x (xs:tls) -> (x:xs):xs:tls) [[]]

Вроде работает :-)
Кстати, никто не знает, почему обязательно надо делать paraFac (5::Int), а то GHCi выдаёт ошибку?


Кстати, там во второй главе ошибка. В самом конце при описании параморфизма (скобки, разумеется, колючие):

tails = (Cons(Nil, Nil), ⊕), где a⊕(as,tls) = Cons(Cons(a,as),tls)

это неверно, потому что даёт только первый tail (сам список), а не сохраняет последующие. Надо:

a⊕(as,tls) = Cons(Cons(a,as),Cons(as,tls))

Comments

[potan.livejournal.com]

(5::Int)
Потому-что 5 - это что-то класса Integral. А про тип ghc ни чего еще ни чего не знает.

[lomeo.livejournal.com]

А для класса Num исключение сделали?
Почему не обязательно писать (5::Int)+5?

[potan.livejournal.com]

Да, непонятно :-).
Мне это (http://dmitri83.livejournal.com/148109.html) вспомнилось.

[lomeo.livejournal.com]

Да, я тоже об этом думал.
В общем в haskell98-report #4.3.4

Ambiguities in the class Num are most common, so Haskell provides another way to resolve them—
with a default declaration...

Таким образом, 5 будет читаться по дефолту как Integer только в контексте операций Num.

На самом деле это неправда, также работает, например 2/3 - Fractional, но смысл ясен - это только для стандартных классов :-(

Надеюсь, нигде не наврал.