Drobiażdżki

Małe wprawki w Haskellu i drobniutkie zabawy matematyczne. To moje rozrywki ostatnio, kiedy akurat mam trochę wolnego czasu, nie oglądam telewizji i nie czytam jednej z dwóch książek których coś nie mogę skończyć.
Zabawa wzięła początek z zagadek o jakich kiedyś na blogu wspomniałem.

Na początek - jak liczbę z zakresu [0,1) zamienić na jej rozwinięcie dziesiętne, a więc, (być może nieskończony) strumień cyfr {0,...,9}?
Można tak:
Bierzemy x.
Jeżeli x równa się 0, kończymy wypisując 0, jeśli nie to:
Mnożymy razy 10. Mamy 10*x.
Bierzemy część całkowitą. Mamy [10*x] (tu [_] oznacza funkcję int: R->Int). Wypisujemy.
W końcu z liczbą (10*x-[10*x]) robimy to samo.

W efekcie produkujemy, być może nieskończony (nawet dla wymiernego argumentu), ciąg cyfr.
Jak zamienić na rozwiniecie przy innej podstawietawie np. 2? To proste: funkcję x->10*x w powyższym schemacie zastąpić przez x->2*x.

Zagadka: co ma wspólnego z tym co napisałem poniższy obrazek:

Ułamek łańcuchowy, np taki: 1/(a_1+1/(a_2+1/(a_3+1/a_4))) będę reprezentował jako listę liczb naturalnych, np. taką: [a_1, a_2, a_3, a_4]. Oczywiście lista może być nieskończona.

Teraz: jak liczbę z zakresu [0,1) zamienić na ułamek łańcuchowy?
Można tak:

Bierzemy x.
Jeżeli x równa się 0, kończymy wypisując 0, jeśli nie to:
Dzielimy 1 przez x. Mamy 1/x.
Bierzemy część całkowitą. Mamy [1/x] ([_] znowu oznacza funkcję int: R->Int). Wypisujemy.
W końcu z liczbą (1/x-[1/x]) robimy to samo.

W efekcie produkujemy, być może nieskończony (ale nie dla wymiernego argumentu, dowód: ćwiczenie) ciąg liczb.

Zagadka (podobna do poprzedniej): co ma wspólnego z tym co napisałem poniższy obrazek:

Spróbuję ten ogólny schemat zapisać w Haskellu, ale:
- będę używał będę typu Rational w miejsce liczb rzeczywistych
- nie będę sprawdzał zakresu wejść (to ważne w życiu ale nudne, więc chociaż na blogu zluzuję)

W poniższym kodzie:
numscheme - to nasz schemat
n_ary - ogólny schemat rozwinięcia pozycyjnego
binary - szczególny przypadek n_ary dla n = 2
decimal - szczególny przypadek n_ary dla n = 2
confrac - rozwinięcie w ułamek łańcuchowy


Kod:

import Ratio ( numerator, denominator, (%) )

numscheme :: Rational -> (Rational -> Rational) -> [Integer]

numscheme 0 _ = []
numscheme x f = y : numscheme( (f x) - fromInteger y) f where
y = div (numerator$z) (denominator$z)
z = f x

n_ary :: Integer -> Rational -> [Integer]
n_ary n s = numscheme s ((toRational n)*)

binary :: Rational -> [Integer]
binary = n_ary 2

decimal :: Rational -> [Integer]
decimal = n_ary 10

confrac :: Rational -> [Integer]
confrac s = numscheme s (1/)

Na deser poznęcajmy się nad liczbą (229/232). Mój kalkulator windowsowy daje przybliżenie: 0,98706896551724137931034482758621

Popatrzmy na nasz drobiażdżek w działaniu:

Main> take 40 $ binary (229/232)
[1,1,1,1,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,0,1,1,0,1,0,0,1,1,1,1,0,1,1,1,0,0,1,0,1,1]
Main> take 40 $ decimal (229/232)
[9,8,7,0,6,8,9,6,5,5,1,7,2,4,1,3,7,9,3,1,0,3,4,4,8,2,7,5,8,6,2,0,6,8,9,6,5,5,1,7]
Main> confrac (229/232)
[1,76,3]

Tyle na dziś. More to come...