Это можно было бы использовать для удобства определения функций на
указанном интервале (назовем его 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
насколько я понимаю, простого пути нет. Я бы сказал, что даже не очень
сложного нет. Есть только очень сложный. И даже очень сложный не будет
совсем удовлетворительным, поскольку по крайней мере не самая
тривиальная арифметика уже неразрешима.
Т.е. когда ты будешь вызывать свою функцию с переменной, а не с
константой, доказать, что значение этой переменной лежит в нужном
интервале - это задача theorem prover'а и задача непростая.
Хаскел может в некоторой степени следить за выполнением арифметических
свойств. Для этого нужно эмулировать числа (в простом случае,
натуральные) типами. Вершин эта мысль достигла в работах Олега Киселева,
ты без труда найдешь их в интернете просто по его имени (латиницой).
Но мне кажется, что это страшная монструозная пушка для несчастных
воробьев. К тому же, это скорее игрушка для ума, нежели практически
полезная вещь (на данном этапе и в контексте Хаскела). Код может
превратиться в нечто монструозное, а написание кода в неравную битву с
type checker'ом.
Погугли haskell type arithmetic
--
Daniil Elovkov
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
> 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]
Тогда видимо, эта затея дальнейшего большого смысла иметь не будет. А
предложенное решение будет вполне достаточным.
Мне же тогда придется перепостановить (или скорее, упростить) задачу:
нужно определять разные функции, скажем типа Int->Int и не
заморачиваться заранее диапазоном аргументов, но при выполнении (бог с
компиляцией) при каждом вызове таких функций как-то делать
единообразно проверку на вхождение аргумента в требуемый диапазон.,
Можно.
$ 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
Есть два варианта реализации функции fromInteger для типа Int --
выбрасывать исключение как в MyInt, или молча приводить к диапазону
Int.
Почему был выбран второй вариант? Не в последнюю очередь из-за того,
что он влечет за собой ряд приятных и полезных свойств, например
(fromInteger (a+b) :: Int) == fromInteger a + fromInteger b
Нет никакого сюрприза. Если вы перечитаете мое изначальное сообщение:
"Поскольку конструктор данных MyInt не экспортируется, создать
экземпляр типа MyInt в обход проверки на диапазон невозможно."
(В вашем случае замените MyInt на MakeNatural). Идея состояла в том, что
область видимости конструктора данных -- один маленький модуль, в
котором мы должны строго контролировать его использование и выбрасывать
в случае чего исключение.
А ваша "функция", благодаря instance Num Natural, должна была бы
выглядеть просто как
f :: Natural -> Natural
f x = -1
> Но наверно, это плохой путь, если любой может использовать не функцию,
> а конструктор.
Да, решением этой проблемы и служит абстрактный тип данных.
Я сейчас как раз осилив "борьбу с созданием новых типов", разбираюсь с
АТД.
Кстати, Ваш пример (в моем контесксте не сработает):
*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]
> - Показать цитируемый текст -
О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫ 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
Я вас не совсем понимаю. Почему не сработает? Разве это не есть желаемый
эффект?
> Таким образом, только используя конструкторы данных, мы не можем
> создать многие типы: положительные целые (в моем примере 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, он работает с ними как с обычными целыми числами.
Пардон, должно быть
data BinTree a = Leaf a | Node !(BinTree a) !(BinTree a)
> > Кстати, Ваш пример (в моем контесксте не сработает):
>
> > *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 в этом смысле как-то стоит особо, тут нет проблем задать
рекурсию)
Мне кажется, вы мне уже задавали этот вопрос и я уже на него отвечал.
Попробую другими словами. 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
Я тоже пробовал другими словами!! ;-) (я всего лишь утверждал, что
недостаточно было сделано проверок, или слишком много было разрешено
пользователю и я смог построить пример где удалось построить пример с
отрицатльными натуральными числами, что есть плохо -- и сам этому
удивился, и стал разбираться дальше и глубже)
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
Спасибо за очень ценную информацию!! Это конечно, не ожидаемое,
слишком сложное, но теперь интересно понять про катаморфизм, и где
почитать подробннее, желательно по русски?!
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]
--
Дима
Но только сам тип
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>:
Учить матчасть надо. Советую начать с lambda calculus, дальше основы
теории типов, потом dependent types. Без научной подготовки так ничего
не разберешь.
С уважением,
Петр.
Да нет, по-моему все корректно. Как вы сами видите, referential
transparency приводит к тому, что семантической разницы (в смысле
денотационной семантики) между вашим "графом" и деревом никакой нет.
Поэтому двойка и присутствует в списке дважды.
Я же имел в виду принципиально циклическую структуру. Если угодно,
циклический ориентированный граф. А в вашем примере -- даг.
> > [1]http://en.wikipedia.org/wiki/Catamorphism
>
> Спасибо за очень ценную информацию!! Это конечно, не ожидаемое,
> слишком сложное, но теперь интересно понять про катаморфизм, и где
> почитать подробннее, желательно по русски?!
Например, статья "Functional Programming with Bananas, Lenses, Envelopes
and Barbed Wire". Я не в курсе, переводили ли ее на русский.
Реализацию типа 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
--
Дима
О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫О©╫. О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫, О©╫О©╫О©╫О©╫О©╫ О©╫О©╫ _О©╫_О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫_
О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ -- О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫? О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ --
О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫.
О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫. О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫, О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫.
О©╫.О©╫. О©╫О©╫О©╫О©╫ О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫ О©╫ О©╫О©╫О©╫, О©╫О©╫ О©╫О©╫О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫, О©╫О©╫О©╫ О©╫О©╫О©╫ О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫
О©╫О©╫О©╫О©╫ 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