[spbhug] Ограниченные типы -- возможно?

28 views
Skip to first unread message

nsk.coder

unread,
May 25, 2010, 9:43:44 AM5/25/10
to SPb Haskell User Group
Есть вопрос. Хочется задать тип, который был бы отрезком, скажем,
числового типа. Ну, в самом простом случае -- отрезком в типе Int,
однако со своим именем и именно как тип. Например, значения нового
типа были бы отрезком вида [12; 37] -- т.е. целыми в указанном
интервале.

Это можно было бы использовать для удобства определения функций на
указанном интервале (назовем его MyInt):

f :: MyInt -> Int
f 13 = 4
f 22 = 5
f _ = 0

и не беспокоится о проверке того, чтобы при определении или при
применении функции аргумент лежал в интервале от 12 до 37. По
аналогии, как если бы для функции с типом Int -> Int мы попытались
бы использовать нецелый аргумент -- исполняющая система сама выдаст
ошибку.

Далее можно было бы обобщить: кроме отрезков использовать
полуинтервалы и интервалы, или просто конечные множества, и не только
в типе Int, но и в Integer или даже Double, да и вообще в каких-либо
иных типах. Соответственно, полезно еще иметь и наличие параметризма
для такого типа (наш тип был бы похож на, скажем, MyInt (12, 37)).

Я понимаю, что наиболее близким подходом было бы использование
конкретных списков. Но в данном случае не нужен весь функционал
списков, а нужно только лишь передать на компилятор и на исполняющую
систему проверку того, что используемые данные лежат в требуемом
множестве.

Может быть, кто-нибудь подскажет, как это можно организовать? Или это
уже есть?

--
Отправить сообщение в SPb HUG: spb...@googlegroups.com
Отменить подписку: spbhug-un...@googlegroups.com
Страница группы: http://groups.google.com/group/spbhug?hl=ru

Daniil Elovkov

unread,
May 25, 2010, 10:03:39 AM5/25/10
to spb...@googlegroups.com

Да поправят меня знающие, но

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

Т.е. когда ты будешь вызывать свою функцию с переменной, а не с
константой, доказать, что значение этой переменной лежит в нужном
интервале - это задача theorem prover'а и задача непростая.

Хаскел может в некоторой степени следить за выполнением арифметических
свойств. Для этого нужно эмулировать числа (в простом случае,
натуральные) типами. Вершин эта мысль достигла в работах Олега Киселева,
ты без труда найдешь их в интернете просто по его имени (латиницой).

Но мне кажется, что это страшная монструозная пушка для несчастных
воробьев. К тому же, это скорее игрушка для ума, нежели практически
полезная вещь (на данном этапе и в контексте Хаскела). Код может
превратиться в нечто монструозное, а написание кода в неравную битву с
type checker'ом.

Погугли haskell type arithmetic


--
Daniil Elovkov

Dmitry Olshansky

unread,
May 25, 2010, 10:51:56 AM5/25/10
to spb...@googlegroups.com
Ясно, что можно сделать
> data Val_InInterval = Val_InInterval { val :: Int, intMin :: Int, intMax :: Int }
 
и определить
> instance Num Val_InInterval
 
где реализовать проверки с требуемой обработкой исключительных ситуаций.
 
Для ответа на вопрос про проверку при компиляции надо, наверное, понимать, какие функции должны применяться к типу. Для приведенного примера достаточно перечисления:
 
data Int_12_37 = Int_12_37_12 | Int_12_37_13 | ... | Int_12_37_37
 
f :: Int_12_37 -> Int
f Int_12_37_13 = 4
f Int_12_37_22 = 5
f _   = 0
 
Такое c Template Haskell'ем можно, вероятно, сделать удобоваримым.
 
Видимо, имеется в виду что-то большее?
 
 
 
 
 
 
25 мая 2010 г. 18:03 пользователь Daniil Elovkov <daniil....@gmail.com> написал:

Roman Cheplyaka

unread,
May 25, 2010, 12:09:53 PM5/25/10
to spb...@googlegroups.com
* nsk.coder <nsk....@gmail.com> [2010-05-25 06:43:44-0700]

> Есть вопрос. Хочется задать тип, который был бы отрезком, скажем,
> числового типа. Ну, в самом простом случае -- отрезком в типе Int,
> однако со своим именем и именно как тип. Например, значения нового
> типа были бы отрезком вида [12; 37] -- т.е. целыми в указанном
> интервале.

module MyInt (MyInt) where

newtype MyInt = MyInt { fromMy :: Int } deriving (Eq,Ord)

myInt :: Int -> MyInt
myInt x | x >= 12 && x <= 37 = MyInt x
| otherwise = error "out of bounds"

liftInt f = myInt . f . fromMy
liftInt2 f a b = myInt $ f (fromMy a) (fromMy b)

instance Num MyInt where
(+) = liftInt2 (+)
(*) = liftInt2 (*)
(-) = liftInt2 (-)
negate = liftInt negate
signum = liftInt signum
abs = liftInt abs
fromInteger = myInt . fromInteger

instance Show MyInt where
showsPrec n = showsPrec n . fromMy

---

*MyInt> 20 :: MyInt
20

*MyInt> 10 :: MyInt
*** Exception: out of bounds

Поскольку конструктор данных MyInt не экспортируется, создать экземпляр
типа MyInt в обход проверки на диапазон невозможно.

--
Roman I. Cheplyaka :: http://ro-che.info/
"Don't let school get in the way of your education." - Mark Twain

Ivan Tarasov

unread,
May 25, 2010, 12:49:13 PM5/25/10
to spb...@googlegroups.com
Я полагаю, что такой тип в принципе возможно сделать в Haskell'е, только большой проблемой будет его использование: оно будет слишком неудобным/непрактичным.

Может иметь смысл глянуть на Agda, где такие типы с лёгкостью задаются и проверяются на стадии трансляции кода на Agda в Haskell (т.е. фактически в compile-time).

Иван

2010/5/25 nsk.coder <nsk....@gmail.com>

nsk.coder

unread,
May 25, 2010, 11:22:40 PM5/25/10
to SPb Haskell User Group
Roman, мне очень понравилось Ваше решение, и видимо, его было бы
вполне достаточно, однако
одно из главных условий не сработало: т.е. во время исполнения
проверки на принадлежность указанному интервалу не происходит:

> let f :: MyInt->Int; f _ = 0
> f 13
0
> f 20
0
> f 1
0
t> :t f
f :: MyInt -> Int
> f (2.1)

<interactive>:1:3:
No instance for (Fractional MyInt)
...

Видим, что при вызове функции f от аргумента 1 вовзращается 0, однако
нам такого не надо!

Можно как-то подправить?


On 25 май, 23:09, Roman Cheplyaka <r...@ro-che.info> wrote:
> * nsk.coder <nsk.co...@gmail.com> [2010-05-25 06:43:44-0700]

Denis Moskvin

unread,
May 25, 2010, 11:44:47 PM5/25/10
to spb...@googlegroups.com
Ну так язык ленивый; для встроенных типов то же самое
Prelude> let f :: Int->Int; f _ = 0
Prelude> f 1000000000000000000000000000000000000
0
(аргумент не лезет в Int, но это не помеха). Если хочется форсировать проверку, то можно как-то так
f a = seq a 0

26 мая 2010 г. 6:22 пользователь nsk.coder <nsk....@gmail.com> написал:

Dmitry Olshansky

unread,
May 26, 2010, 1:35:49 AM5/26/10
to spb...@googlegroups.com
Маленькое замечание - для Int (в отличие от MyInt) проверки нет в любом случае:
 
Prelude> let a =1000000000000000000::Int
Prelude> :t a
a :: Int
Prelude> a
-1486618624

26 мая 2010 г. 7:44 пользователь Denis Moskvin <dmos...@gmail.com> написал:

nsk.coder

unread,
May 26, 2010, 5:03:00 AM5/26/10
to SPb Haskell User Group
Вот же неожиданная засада! (а это точно не глюк в реализации??)

Тогда видимо, эта затея дальнейшего большого смысла иметь не будет. А
предложенное решение будет вполне достаточным.

Мне же тогда придется перепостановить (или скорее, упростить) задачу:
нужно определять разные функции, скажем типа Int->Int и не
заморачиваться заранее диапазоном аргументов, но при выполнении (бог с
компиляцией) при каждом вызове таких функций как-то делать
единообразно проверку на вхождение аргумента в требуемый диапазон.,

Roman Cheplyaka

unread,
May 26, 2010, 5:25:06 AM5/26/10
to SPb Haskell User Group
On May 26, 6:22 am, "nsk.coder" <nsk.co...@gmail.com> wrote:
> Roman, мне очень понравилось Ваше решение, и видимо, его было бы
> вполне достаточно, однако
> одно из главных условий не сработало: т.е. во время исполнения
> проверки на принадлежность указанному интервалу не происходит:
>
> > let f :: MyInt->Int; f _ = 0
> > f 13
> 0
> > f 20
> 0
> > f 1
>
> 0
> t> :t f
> f :: MyInt -> Int
>
> > f (2.1)
>
> <interactive>:1:3:
>     No instance for (Fractional MyInt)
> ...
>
> Видим, что при вызове функции f от аргумента 1 вовзращается 0, однако
> нам такого не надо!
>
> Можно как-то подправить?

Можно.
$ ghci -XBangPatterns MyInt.hs
*MyInt> let f :: MyInt -> Int; f !_ = 0
*MyInt> f 13
0
*MyInt> f 1


*** Exception: out of bounds

(Естественно, того же можно достичь и без BangPatterns, просто так
красивее смотрится.)

Но тут просто дело в том, что вы взяли вырожденную функцию
(константу). В примере, который вы приводили вначале, есть паттерн
матчинг над аргументом, поэтому функция автоматически перестает быть
ленивой.

*MyInt> let f :: MyInt -> Int; f 13 = 4; f 22 = 5; f _ = 0
*MyInt> f 13
4
*MyInt> f 1

Roman Cheplyaka

unread,
May 26, 2010, 6:18:09 AM5/26/10
to SPb Haskell User Group
On May 26, 8:35 am, Dmitry Olshansky <olshansk...@gmail.com> wrote:
> Маленькое замечание - для Int (в отличие от MyInt) проверки нет в любом
> случае:
>
> Prelude> let a =1000000000000000000::Int
> Prelude> :t a
> a :: Int
> Prelude> a
> -1486618624

Есть два варианта реализации функции fromInteger для типа Int --
выбрасывать исключение как в MyInt, или молча приводить к диапазону
Int.
Почему был выбран второй вариант? Не в последнюю очередь из-за того,
что он влечет за собой ряд приятных и полезных свойств, например
(fromInteger (a+b) :: Int) == fromInteger a + fromInteger b

Roman Cheplyaka

unread,
Oct 30, 2010, 8:21:33 AM10/30/10
to nsk.coder, spb...@googlegroups.com
* nsk.coder <nsk....@gmail.com> [2010-10-30 03:09:22-0700]
> Роман, я обнаружил еще одну засаду!!
>
> Вот беру решение типа Вашего (точнее, в Вашем стиле допиленный пример
> из Мягкого Введение в Haskell:
>
>
> newtype Natural = MakeNatural Integer deriving (Eq,Ord)
>
> toNatural :: Integer -> Natural
> toNatural x | x < 0 = error "There is no negative natural numbers!"
> | otherwise = MakeNatural x
>
> fromNatural :: Natural -> Integer
> fromNatural (MakeNatural i) = i
>
> instance Num Natural where
> fromInteger = toNatural
> x + y = toNatural (fromNatural x + fromNatural y)
> x - y = toNatural (fromNatural x - fromNatural y)
> x * y = toNatural (fromNatural x * fromNatural y)
>
> ...
>
> Но попробуем задать:
>
> >let f :: Natural -> Natural; f x = MakeNatural (-1)
> >f 2
> - 1
>
> Сюрприз!! Добиваясь корректной работы для правой части уравнения,
> задающего функцию, левая часть-то совсем осталась неучтена!!!

Нет никакого сюрприза. Если вы перечитаете мое изначальное сообщение:

"Поскольку конструктор данных MyInt не экспортируется, создать
экземпляр типа MyInt в обход проверки на диапазон невозможно."

(В вашем случае замените MyInt на MakeNatural). Идея состояла в том, что
область видимости конструктора данных -- один маленький модуль, в
котором мы должны строго контролировать его использование и выбрасывать
в случае чего исключение.

А ваша "функция", благодаря instance Num Natural, должна была бы
выглядеть просто как

f :: Natural -> Natural
f x = -1

> Но наверно, это плохой путь, если любой может использовать не функцию,
> а конструктор.

Да, решением этой проблемы и служит абстрактный тип данных.

nsk.coder

unread,
Nov 12, 2010, 1:11:05 PM11/12/10
to SPb Haskell User Group
Роман, с большим удовольствием читаю Ваши посты касательно Haskell,
спасибо за ответ!

Я сейчас как раз осилив "борьбу с созданием новых типов", разбираюсь с
АТД.

Кстати, Ваш пример (в моем контесксте не сработает):

*Main> let f:: Natural -> Natural; f x = (-1)
*Main> f 2
*** Exception: There is no negative natural numbers!

А вот то, что я попробовал, вроде дает нужный глюк:

*Main> let g:: Natural -> Natural; g x = MakeNatural (-1)
*Main> g 2
-1

Ну да ладно.

У меня в связи с АДТ и сокрытием конструкторов данных, а также их
возможностями вообще вопросы есть.

ПРОБЛЕМА: конструкторы данных реально имеют не так много возможностей
в языке Haskell, их синтаксис подобен КС-грамматикам, возможностей как
при задании функций (например ставить предикаты-охрану) -- нет.

Таким образом, только используя конструкторы данных, мы не можем
создать многие типы: положительные целые (в моем примере Natural),
деревья!!! (все что я читал, начиная от статьи в Мягком введении в
Haskell до описания соответствующего модуля Tree -- это не деревья,
так мы можем построить циклические структуры), всякие подмножества
целых, например тип простых чисел, тип чисел Фиббоначи и т.п.

Обходим данную проблему с помощью модуля с АДТ и сокрытием
нежелательных конструкторов. Тип будет создан, вместо конструкторов
данных предлагаем методы и перегруженные функции, где можем сделать
нужные нам проверки и контроль.

Однако, таким образом, мы отбираем у пользователя pattern matching и
возможность писать произвольные рекурсивные функции над значениями из
заданного типа.

И что ж теперь делать? Как объединить мощь АДТ с возможностью
использовать pattern matching?

On 30 окт, 18:21, Roman Cheplyaka <r...@ro-che.info> wrote:
> * nsk.coder <nsk.co...@gmail.com> [2010-10-30 03:09:22-0700]

> - Показать цитируемый текст -

Daniil Elovkov

unread,
Nov 12, 2010, 4:23:49 PM11/12/10
to spb...@googlegroups.com, nsk.coder
On 12.11.2010 21:11, nsk.coder wrote:
> ...
> О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ pattern matching О©╫
> О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫
> О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫.
>
> О©╫ О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫? О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
> О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ pattern matching?

О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫ view patterns

http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/syntax-extns.html#view-patterns

http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns

О©╫ О©╫О©╫О©╫ pattern guards

http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/syntax-extns.html#pattern-guards

О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫(О©╫) О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
(О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ view), О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫ view.

О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫, О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫.


>
> On 30 О©╫О©╫О©╫, 18:21, Roman Cheplyaka<r...@ro-che.info> wrote:
>> * nsk.coder<nsk.co...@gmail.com> [2010-10-30 03:09:22-0700]
>>
>>
>>
>>
>>

>>> О©╫О©╫О©╫О©╫О©╫, О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫!!
>>
>>> О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ (О©╫О©╫О©╫О©╫О©╫О©╫, О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫
>>> О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ Haskell:


>>
>>> newtype Natural = MakeNatural Integer deriving (Eq,Ord)
>>
>>> toNatural :: Integer -> Natural
>>> toNatural x | x< 0 = error "There is no negative natural numbers!"
>>> | otherwise = MakeNatural x
>>
>>> fromNatural :: Natural -> Integer
>>> fromNatural (MakeNatural i) = i
>>
>>> instance Num Natural where
>>> fromInteger = toNatural
>>> x + y = toNatural (fromNatural x + fromNatural y)
>>> x - y = toNatural (fromNatural x - fromNatural y)
>>> x * y = toNatural (fromNatural x * fromNatural y)
>>
>>> ...
>>

>>> О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫:


>>
>>>> let f :: Natural -> Natural; f x = MakeNatural (-1)
>>>> f 2
>>> - 1
>>

>>> О©╫О©╫О©╫О©╫О©╫О©╫О©╫!! О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫,
>>> О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫-О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫!!!
>>
>> О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫:
>>
>> "О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ MyInt О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫
>> О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ MyInt О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫."
>>
>> (О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ MyInt О©╫О©╫ MakeNatural). О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫, О©╫О©╫О©╫
>> О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ -- О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫, О©╫
>> О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
>> О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫.
>>
>> О©╫ О©╫О©╫О©╫О©╫ "О©╫О©╫О©╫О©╫О©╫О©╫О©╫", О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ instance Num Natural, О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫
>> О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫


>>
>> f :: Natural -> Natural
>> f x = -1
>>

>>> О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫,
>>> О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫.
>>
>> О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫.
>
>> - О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ -
>


--
Daniil Elovkov

Roman Cheplyaka

unread,
Nov 12, 2010, 6:16:12 PM11/12/10
to spb...@googlegroups.com
* nsk.coder <nsk....@gmail.com> [2010-11-12 10:11:05-0800]

> Кстати, Ваш пример (в моем контесксте не сработает):
>
> *Main> let f:: Natural -> Natural; f x = (-1)
> *Main> f 2
> *** Exception: There is no negative natural numbers!

Я вас не совсем понимаю. Почему не сработает? Разве это не есть желаемый
эффект?

> Таким образом, только используя конструкторы данных, мы не можем
> создать многие типы: положительные целые (в моем примере Natural),

Почему же все-таки не можем?

> деревья!!! (все что я читал, начиная от статьи в Мягком введении в
> Haskell до описания соответствующего модуля Tree -- это не деревья,
> так мы можем построить циклические структуры),

Например, можно сделать конструктор дерева строгим, тогда оно не будет
позволять циклы. (Точнее, любой циклический граф будет эквивалентен _|_).

data BinTree a = Leaf a | Node !(Tree a) !(Tree a)

> всякие подмножества
> целых, например тип простых чисел, тип чисел Фиббоначи и т.п.

Аналогично натуральным числам.

> Обходим данную проблему с помощью модуля с АДТ и сокрытием
> нежелательных конструкторов. Тип будет создан, вместо конструкторов
> данных предлагаем методы и перегруженные функции, где можем сделать
> нужные нам проверки и контроль.
>
> Однако, таким образом, мы отбираем у пользователя pattern matching и

Почему же?

*Main> let x = 42 :: Natural
*Main> :t x
x :: Natural
*Main> case x of { 42 -> "cool"; _ -> "not cool"; }
"cool"

Пользователь вообще не должен знать о каких-то особенных конструкторах
для Natural, он работает с ними как с обычными целыми числами.

nsk.coder

unread,
Nov 13, 2010, 5:43:20 AM11/13/10
to SPb Haskell User Group
Daniil, спасибо за ссылки! Для меня это новость, но нужно разбираться,
сходу понять трудно...

> view patterns
>
> http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/syntax-extns....
>
> http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns
>
> pattern guards
>
> http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/syntax-extns....
>
> ( ) ,
> ( view), ,
> view.
>

> --
> Daniil Elovkov

Roman Cheplyaka

unread,
Nov 13, 2010, 5:49:12 AM11/13/10
to spb...@googlegroups.com
* Roman Cheplyaka <ro...@ro-che.info> [2010-11-13 01:16:12+0200]

> data BinTree a = Leaf a | Node !(Tree a) !(Tree a)

Пардон, должно быть

data BinTree a = Leaf a | Node !(BinTree a) !(BinTree a)

nsk.coder

unread,
Nov 13, 2010, 6:17:07 AM11/13/10
to SPb Haskell User Group
Roman, я не смогу сразу ответить на все пункты, квалификации не
хватает, надо подумать. Но по некоторым попробую:

> > Кстати, Ваш пример (в моем контесксте не сработает):
>
> > *Main> let f:: Natural -> Natural; f x = (-1)
> > *Main> f 2
> > *** Exception: There is no negative natural numbers!
>
> Я вас не совсем понимаю. Почему не сработает? Разве это не есть желаемый
> эффект?

Нет, глюк в том, что определяем g x = MakeNatural (-1) и интерпретатор
это проглатывает, вместо того сообщить что нет отрицательных
натуральных чисел. В Вашем примере, все поведение ожидаемо, нам
сообщают, что отрицательных целых нет -- ну так и должно быть.

> > Таким образом, только используя конструкторы данных, мы не можем
> > создать многие типы: положительные целые (в моем примере Natural),
>
> Почему же все-таки не можем?

Я пока не очень понял Ваш ответ про конструкторы данных с флажками
строгости, насколько это поможет.
Но по сути: синтаксис конструкторов данных довольно беден и мы не
можем определить только ими что-то слишком сложное.

Как мы определим только конструктором данных тип простых чисел?

В некоторых языках (говорят, в Прологе так), для этого можно
использовать что-то вроде конструкторов с предикатами, которые
позволяют создавать сложные вещи.


> Например, можно сделать конструктор дерева строгим, тогда оно не будет
> позволять циклы. (Точнее, любой циклический граф будет эквивалентен _|_).

>   data BinTree a = Leaf a | Node !(Tree a) !(Tree a)


пока не понял.. :(

> Аналогично натуральным числам.

как это?

> > Обходим данную проблему с помощью модуля с АДТ и сокрытием
> > нежелательных конструкторов. Тип будет создан, вместо конструкторов
> > данных предлагаем методы и перегруженные функции, где можем сделать
> > нужные нам проверки и контроль.
>
> > Однако, таким образом, мы отбираем у пользователя pattern matching и
>
> Почему же?
>
>     *Main> let x = 42 :: Natural
>     *Main> :t x
>     x :: Natural
>     *Main> case x of { 42 -> "cool"; _ -> "not cool"; }
>     "cool"


Действительно...
Ну хорошо, а как с рекурсией?

например, создаем АДТ для одностороннего списка, прячем от
пользователя конструктор данных ":", взамен даем методы pop и push.

Ну и как пользователь задаст рекурсию по списку, например как ему
самому задать функцию length? Конечно, как-то это можно обойти, но
ведь хочется, чтобы это не сильно отличалось от уже привычного

length [] = 0
length (x:xs) = 1 + length xs

>
> Пользователь вообще не должен знать о каких-то особенных конструкторах
> для Natural, он работает с ними как с обычными целыми числами.

согласен, вот только хотелось бы чтобы у пользователя остались
привычные средства создания рекурсии.
Как задать рекурсию и более-менее сложный pattern matching без
конструкторов данных?
(Natural в этом смысле как-то стоит особо, тут нет проблем задать
рекурсию)

Roman Cheplyaka

unread,
Nov 13, 2010, 6:51:01 AM11/13/10
to spb...@googlegroups.com
* nsk.coder <nsk....@gmail.com> [2010-11-13 03:17:07-0800]

> Roman, я не смогу сразу ответить на все пункты, квалификации не
> хватает, надо подумать. Но по некоторым попробую:
>
> > > Кстати, Ваш пример (в моем контесксте не сработает):
> >
> > > *Main> let f:: Natural -> Natural; f x = (-1)
> > > *Main> f 2
> > > *** Exception: There is no negative natural numbers!
> >
> > Я вас не совсем понимаю. Почему не сработает? Разве это не есть желаемый
> > эффект?
>
> Нет, глюк в том, что определяем g x = MakeNatural (-1) и интерпретатор
> это проглатывает, вместо того сообщить что нет отрицательных
> натуральных чисел.

Мне кажется, вы мне уже задавали этот вопрос и я уже на него отвечал.
Попробую другими словами. MakeNatural -- деталь реализации. Она
сокрыта. Результат выполнения MakeNatural, так как я его определил,
таков:

> MakeNatural (-1)

<interactive>:1:0: Not in scope: data constructor `MakeNatural'


> Как мы определим только конструктором данных тип простых чисел?

В примере с натуральными числами заменяем проверку положительности
проверкой на простоту.

> > Например, можно сделать конструктор дерева строгим, тогда оно не будет
> > позволять циклы. (Точнее, любой циклический граф будет эквивалентен _|_).
>

> >   data BinTree a = Leaf a | Node !(BinTree a) !(BinTree a)
>
>
> пока не понял.. :(

Попробуем создать в рамках этого типа граф с циклом и посмотрим, что
выйдет.

let tree = Node (Leaf 0) tree
in case tree of
Node {} -> "node"
Leaf {} -> "leaf"

Значение tree уйдет в бесконечный цикл, как только мы попытаемся его
вычислить. То есть создать цикл нам не удалось

> > > Однако, таким образом, мы отбираем у пользователя pattern matching и
> >
> > Почему же?
> >
> >     *Main> let x = 42 :: Natural
> >     *Main> :t x
> >     x :: Natural
> >     *Main> case x of { 42 -> "cool"; _ -> "not cool"; }
> >     "cool"
>
>
> Действительно...
> Ну хорошо, а как с рекурсией?
>
> например, создаем АДТ для одностороннего списка, прячем от
> пользователя конструктор данных ":", взамен даем методы pop и push.
>
> Ну и как пользователь задаст рекурсию по списку, например как ему
> самому задать функцию length? Конечно, как-то это можно обойти, но
> ведь хочется, чтобы это не сильно отличалось от уже привычного
>
> length [] = 0
> length (x:xs) = 1 + length xs

Это решается предоставлением катаморфизма [1].

Примеры (из Prelude):

для нерекурсивных типов:

maybe
:: b -- обработчик для Nothing
-> (a -> b) -- обработчик для Just
-> Maybe a -- объект паттерн-матчинга
-> b -- результат паттерн-матчинга

either
:: (a -> c) -- обработчик для Left
-> (b -> c) -- обработчик для Right
-> Either a b -- объект паттерн-матчинга
-> c -- результат паттерн-матчинга

для рекурсивных типов:

foldr
:: (a -> b -> b) -- обработчик для (:)
-> b -- обработчик для []
-> [a] -- объект (рекурсивного) паттерн-матчинга
-> b -- результат паттерн-матчинга

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

[1] http://en.wikipedia.org/wiki/Catamorphism

nsk.coder

unread,
Nov 14, 2010, 5:22:51 AM11/14/10
to SPb Haskell User Group
> Мне кажется, вы мне уже задавали этот вопрос и я уже на него отвечал.
> Попробую другими словами.

Я тоже пробовал другими словами!! ;-) (я всего лишь утверждал, что
недостаточно было сделано проверок, или слишком много было разрешено
пользователю и я смог построить пример где удалось построить пример с
отрицатльными натуральными числами, что есть плохо -- и сам этому
удивился, и стал разбираться дальше и глубже)

MakeNatural -- деталь реализации. Она
> сокрыта. Результат выполнения MakeNatural, так как я его определил,
> таков:
>
>     > MakeNatural (-1)
>     <interactive>:1:0: Not in scope: data constructor `MakeNatural'

Я понял достаточно с этим примером, спасибо! Надеюсь, Вы меня понял
тоже.

> > Как мы определим только конструктором данных тип простых чисел?
>
> В примере с натуральными числами заменяем проверку положительности
> проверкой на простоту.

Пардон, это решение как раз понятно с самого первого Вашего поста.
Если мы используем АДТ и вместо конструкторов даем пользователю
методы, тогда вопроса нет.

Я же утверждал, что ТОЛЬКО используя конструкторы данных, вы не
сможете задать, например тип простых чисел или тип чисел Фиббоначи!!
Вы не сможете задать даже положительные целые.


(Более того, мне не нравится, когда в уважаемых книгах и статьях
называют тип "Типом Бинарных дереьвев", но он не таков, а значительно
шире)

> > > Например, можно сделать конструктор дерева строгим, тогда оно не будет
> > > позволять циклы. (Точнее, любой циклический граф будет эквивалентен _|_).
>
> > >   data BinTree a = Leaf a | Node !(BinTree a) !(BinTree a)
>
>

> Попробуем создать в рамках этого типа граф с циклом и посмотрим, что
> выйдет.
>
>   let tree = Node (Leaf 0) tree
>   in case tree of
>       Node {} -> "node"
>       Leaf {} -> "leaf"


А у меня в рамках Вашего примера получился граф с циклом (!!):

a1 = Leaf 1
a2 = Leaf 2
a3 = Leaf 3
b1 = Node a1 a2
b2 = Node a2 a3
b3 = Node b1 b2

Видим, b3 -- вершина цикла, b1 -- его левый последователь, b2 --
правый, a2 -- самый нижний элемент этого цикла из четырех элементов. И
функции типа fringe (описанные в статье "Мягкое введение в Haskell")
работают с этим графом:

*Main> fringe b3
[1,2,2,3]

Правда не корректно, но это потому, что тип описан некорректно.

> Значение tree уйдет в бесконечный цикл, как только мы попытаемся его
> вычислить. То есть создать цикл нам не удалось
>

Однако, удалось!! ;-)

> > Ну хорошо, а как с рекурсией?
> > например, создаем АДТ для одностороннего списка, прячем от
> > пользователя конструктор данных ":", взамен даем методы pop и push.
>
> > Ну и как пользователь задаст рекурсию по списку, например как ему
> > самому задать функцию length? Конечно, как-то это можно обойти, но
> > ведь хочется, чтобы это не сильно отличалось от уже привычного
>
> > length [] = 0
> > length (x:xs) = 1 + length xs
>
> Это решается предоставлением катаморфизма [1].

Эээ, хорошобы подробнее!!! Очень интересно!!!


>
> Примеры (из Prelude):
>
> для нерекурсивных типов:
>
>   maybe
>     :: b        -- обработчик для Nothing
>     -> (a -> b) -- обработчик для Just
>     -> Maybe a  -- объект паттерн-матчинга
>     -> b        -- результат паттерн-матчинга
>
>   either
>     :: (a -> c)   -- обработчик для Left
>     -> (b -> c)   -- обработчик для Right
>     -> Either a b -- объект паттерн-матчинга
>     -> c          -- результат паттерн-матчинга
>
> для рекурсивных типов:
>
>   foldr
>     :: (a -> b -> b) -- обработчик для (:)
>     -> b             -- обработчик для []
>     -> [a]           -- объект (рекурсивного) паттерн-матчинга
>     -> b             -- результат паттерн-матчинга
>
> Любой паттерн-матчинг и (в случае рекурсивного типа данных) любая
> структурная рекурсия могут быть выражены катаморфизмом.
>
> [1]http://en.wikipedia.org/wiki/Catamorphism

Спасибо за очень ценную информацию!! Это конечно, не ожидаемое,
слишком сложное, но теперь интересно понять про катаморфизм, и где
почитать подробннее, желательно по русски?!

Dimitri Timofeev

unread,
Nov 14, 2010, 6:02:11 AM11/14/10
to spb...@googlegroups.com
Добрый день!

2010/11/14 nsk.coder <nsk....@gmail.com>:


> Я же утверждал, что ТОЛЬКО используя конструкторы данных, вы не
> сможете задать, например тип простых чисел или тип чисел Фиббоначи!!
> Вы не сможете задать даже положительные целые.

Отчего же, вполне можно задавать такие типы - если производительность
не важна, конечно.

import Data.List

-- Натуральные числа (числа Пеано)
data Nat = Z | S Nat deriving (Show, Eq, Ord)

zero, one :: Nat
zero = Z
one = S Z

succ :: Nat -> Nat
succ n = S n

plus :: Nat -> Nat -> Nat
plus Z n = n
plus (S m) n = plus m (S n)

mult :: Nat -> Nat -> Nat
mult Z n = Z
mult (S m) n = plus n (mult m n)

natToInteger :: Nat -> Integer
natToInteger Z = 0
natToInteger (S n) = 1 + natToInteger n

-- числа Фибоначчи
data Fib = Fib Nat Nat deriving (Show, Eq, Ord)

fibStart :: Fib
fibStart = Fib one zero

fibNext :: Fib -> Fib
fibNext (Fib a b) = Fib (plus a b) a

fibs :: [Fib]
fibs = fibStart : map fibNext fibs

fibToNat :: Fib -> Nat
fibToNat (Fib a _) = a

fibToInteger :: Fib -> Integer
fibToInteger = natToInteger . fibToNat

--------------
Main> map fibToInteger $ take 10 fibs
[1,1,2,3,5,8,13,21,34,55]

--
Дима

nsk.coder

unread,
Nov 14, 2010, 7:05:53 AM11/14/10
to SPb Haskell User Group
Вот это да!! Красиво!!! Пока правда, как фокус воспринимается...
Подумать надо!! :))

Но только сам тип


data Fib = Fib Nat Nat

Вы определили так, все остальное как АДТ, через методы...

Конструкторы-то не определяют у Вас специфику числе Фиббоначи: Fib Nat
Nat -- как я увижу, что это числа Фиббоначи только в этом месте?

А простые числа? Или произвольное рекурсивно-перечислимое множество?


On 14 ноя, 17:02, Dimitri Timofeev <dimitri.timof...@gmail.com> wrote:
> Добрый день!
>
> 2010/11/14 nsk.coder <nsk.co...@gmail.com>:

pierre

unread,
Nov 14, 2010, 7:09:39 AM11/14/10
to spb...@googlegroups.com
> А простые числа? Или произвольное рекурсивно-перечислимое множество?

Учить матчасть надо. Советую начать с lambda calculus, дальше основы
теории типов, потом dependent types. Без научной подготовки так ничего
не разберешь.

С уважением,
Петр.

Roman Cheplyaka

unread,
Nov 14, 2010, 7:33:29 AM11/14/10
to spb...@googlegroups.com
* nsk.coder <nsk....@gmail.com> [2010-11-14 02:22:51-0800]

> > > > Например, можно сделать конструктор дерева строгим, тогда оно не будет
> > > > позволять циклы. (Точнее, любой циклический граф будет эквивалентен _|_).
> >
> > > >   data BinTree a = Leaf a | Node !(BinTree a) !(BinTree a)
> >
> >
> > Попробуем создать в рамках этого типа граф с циклом и посмотрим, что
> > выйдет.
> >
> >   let tree = Node (Leaf 0) tree
> >   in case tree of
> >       Node {} -> "node"
> >       Leaf {} -> "leaf"
>
>
> А у меня в рамках Вашего примера получился граф с циклом (!!):
>
> a1 = Leaf 1
> a2 = Leaf 2
> a3 = Leaf 3
> b1 = Node a1 a2
> b2 = Node a2 a3
> b3 = Node b1 b2
>
> Видим, b3 -- вершина цикла, b1 -- его левый последователь, b2 --
> правый, a2 -- самый нижний элемент этого цикла из четырех элементов. И
> функции типа fringe (описанные в статье "Мягкое введение в Haskell")
> работают с этим графом:
>
> *Main> fringe b3
> [1,2,2,3]
>
> Правда не корректно, но это потому, что тип описан некорректно.

Да нет, по-моему все корректно. Как вы сами видите, referential
transparency приводит к тому, что семантической разницы (в смысле
денотационной семантики) между вашим "графом" и деревом никакой нет.
Поэтому двойка и присутствует в списке дважды.

Я же имел в виду принципиально циклическую структуру. Если угодно,
циклический ориентированный граф. А в вашем примере -- даг.

> > [1]http://en.wikipedia.org/wiki/Catamorphism
>
> Спасибо за очень ценную информацию!! Это конечно, не ожидаемое,
> слишком сложное, но теперь интересно понять про катаморфизм, и где
> почитать подробннее, желательно по русски?!

Например, статья "Functional Programming with Bananas, Lenses, Envelopes
and Barbed Wire". Я не в курсе, переводили ли ее на русский.

Dimitri Timofeev

unread,
Nov 14, 2010, 2:22:28 PM11/14/10
to spb...@googlegroups.com
Добрый вечер!

Реализацию типа Fib не надо показывать за пределами того модуля, где
этот тип объявлен. Все нужные вещи можно делать, используя только
конструктор типа Fib и функции fibStart, fibNext. Так что это тоже
АТД, если со стороны смотреть.

Глядя только на тип Fib, никак нельзя понять, что это числа Фибоначчи,
Вы правы. нужно знать еще определения функций над этим типом.

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

2010/11/14 nsk.coder <nsk....@gmail.com>:

> --
> Отправить сообщение в SPb HUG: spb...@googlegroups.com
> Отменить подписку: spbhug-un...@googlegroups.com
> Страница группы: http://groups.google.com/group/spbhug?hl=ru

--
Дима

Daniil Elovkov

unread,
Nov 17, 2010, 2:31:23 PM11/17/10
to spb...@googlegroups.com, nsk.coder
On 14.11.2010 15:05, nsk.coder wrote:
> О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫!! О©╫О©╫О©╫О©╫О©╫О©╫О©╫!!! О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫...
> О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫!! :))

>
> О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫
> data Fib = Fib Nat Nat
> О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫...
>
> О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫-О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫: Fib Nat
> Nat -- О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫?

О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ _О©╫_О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫_
О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ -- О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫? О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ --
О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫.

О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫. О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫, О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫.
О©╫.О©╫. О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫, О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫ Fib О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫.

О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫

О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫

О©╫О©╫О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫-О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫, О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
fibStart, О©╫О©╫О©╫О©╫ fibNext. О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫, О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫, О©╫О©╫
О©╫О©╫О©╫О©╫О©╫ _О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫_, О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫.

О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ fibStart О©╫ fibNext О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫. О©╫.О©╫. О©╫О©╫О©╫О©╫О©╫
О©╫О©╫ data Fib = Fib Nat Nat О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫. О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ 2 О©╫О©╫О©╫О©╫О©╫О©╫О©╫ -- О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫.
О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫. О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ (О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫-О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ 2О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫) О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫-О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫. О©╫
О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫.

О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ (О©╫ О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫). О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫. О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ Fib О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫. О©╫О©╫О©╫О©╫О©╫О©╫
fibStart О©╫ fibNext О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫, О©╫ О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫. О©╫.О©╫. О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫.
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫.

О©╫О©╫О©╫О©╫О©╫О©╫, О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫, О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫. О©╫О©╫.
О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫.

О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ (О©╫ О©╫О©╫О©╫О©╫О©╫О©╫-О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫) О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫. О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ -- О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫. О©╫.О©╫.

instance .... => Plus a b c where
...

О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫, О©╫О©╫О©╫ c О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ a О©╫ b. О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫, О©╫О©╫ О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ (О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫). О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫-О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ 2
О©╫О©╫ 10. О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫.

О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫ (О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫) О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ Plus, О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ RSA О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ Fib О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫
(О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫-О©╫О©╫)

data Fib = FibRelated n1 n2 => Fib n1 n2

О©╫О©╫О©╫О©╫О©╫ FibRelated - О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫. О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫.
О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ FibRelated О©╫ О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫,
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫.

О©╫ О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ -- О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫,
О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫-О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫,
О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ A => B О©╫О©╫О©╫О©╫О©╫ О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ A -> B, О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ A О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ B. О©╫.О©╫. О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ A О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫ B, О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫.

О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫-О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ (О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫) О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫. О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫
fibStart, fibNext. О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫. О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫... О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫

О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫.

О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫-О©╫О©╫.


> О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫? О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫-О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫?
>
>
>
>
> On 14 О©╫О©╫О©╫, 17:02, Dimitri Timofeev<dimitri.timof...@gmail.com> wrote:
>> О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫!
>>
>> 2010/11/14 nsk.coder<nsk.co...@gmail.com>:
>>
>>> О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫ О©╫О©╫
>>> О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫!!
>>> О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫.
>>
>> О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫ - О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
>> О©╫О©╫ О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫О©╫.
>>
>> import Data.List
>>
>> -- О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ (О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫)


>> data Nat = Z | S Nat deriving (Show, Eq, Ord)
>>
>> zero, one :: Nat
>> zero = Z
>> one = S Z
>>
>> succ :: Nat -> Nat
>> succ n = S n
>>
>> plus :: Nat -> Nat -> Nat
>> plus Z n = n
>> plus (S m) n = plus m (S n)
>>
>> mult :: Nat -> Nat -> Nat
>> mult Z n = Z
>> mult (S m) n = plus n (mult m n)
>>
>> natToInteger :: Nat -> Integer
>> natToInteger Z = 0
>> natToInteger (S n) = 1 + natToInteger n
>>

>> -- О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫


>> data Fib = Fib Nat Nat deriving (Show, Eq, Ord)
>>
>> fibStart :: Fib
>> fibStart = Fib one zero
>>
>> fibNext :: Fib -> Fib
>> fibNext (Fib a b) = Fib (plus a b) a
>>
>> fibs :: [Fib]
>> fibs = fibStart : map fibNext fibs
>>
>> fibToNat :: Fib -> Nat
>> fibToNat (Fib a _) = a
>>
>> fibToInteger :: Fib -> Integer
>> fibToInteger = natToInteger . fibToNat
>>
>> --------------
>> Main> map fibToInteger $ take 10 fibs
>> [1,1,2,3,5,8,13,21,34,55]
>>
>> --

>> О©╫О©╫О©╫О©╫
>


--
Daniil Elovkov

Reply all
Reply to author
Forward
0 new messages