Declaratieve Talen/Oplossing Stern-Brocot

Verbeteringen altijd welkom.

   data RatGetal = Rat Int Int deriving Show
   
   naarFloat :: RatGetal -> Float
   naarFloat (Rat t n) = fromIntegral(t)/fromIntegral(n)
   
   instance Eq RatGetal where
       (Rat lt ln) == (Rat rt rn) = lt*rn == ln*rt
   
   instance Ord RatGetal where
       (Rat lt ln) <= (Rat rt rn) = lt*rn <= ln*rt
   
   --aangezien de boom oneindig is moeten we geen bladeren voorzien
   data Boom a = Knoop a (Boom a) (Boom a) deriving Show
   
   sbBoom :: Boom RatGetal
   sbBoom = sbDeelBoom (Rat 0 1) (Rat 1 0)
   
   sbDeelBoom :: RatGetal -> RatGetal -> (Boom RatGetal)
   sbDeelBoom (Rat lt ln) (Rat rt rn) =
       let k = Rat (lt+rt) (ln+rn)
           in Knoop k (sbDeelBoom (Rat lt ln) k) (sbDeelBoom k (Rat rt rn))
   
   
   vindGetal :: Float -> Float -> RatGetal
   vindGetal l r = doorzoekBoom l r sbBoom
   
   doorzoekBoom :: Float -> Float -> (Boom RatGetal) -> RatGetal
   doorzoekBoom l r (Knoop k lb rb)
       |naarFloat(k) < l   = doorzoekBoom l r rb
       |naarFloat(k) > r   = doorzoekBoom l r lb
       |otherwise          = k
   
   
   enc :: (Int,Int) -> String
   enc (t,n) = doorzoekBoom2 (Rat t n) sbBoom
   
   doorzoekBoom2 :: Ord a => a -> (Boom a) -> String
   doorzoekBoom2 d (Knoop k lb rb)
       |k < d      = "R" ++ doorzoekBoom2 d rb
       |k > d      = "L" ++ doorzoekBoom2 d lb
       |otherwise  = ""

---

Een oplossing die gebruik maakt van het voorgedefinieerde "Rational"

import Ratio 
data Boom a = Knoop a (Boom a) (Boom a)
	deriving Show
data Rationaal= Rationaal Rational|Inf

noemer::Rationaal->Integer
noemer (Rationaal r)= denominator r
noemer Inf = 0

teller::Rationaal->Integer
teller (Rationaal r)= numerator r
teller Inf = 1

waarde::Rational-> Float
waarde r= (fromInteger (numerator r))/(fromInteger (denominator r))

stern_brocot::Boom Rational
stern_brocot = genereer (Rationaal (0 % 1)) Inf

genereer:: Rationaal -> Rationaal -> Boom Rational
genereer r1 r2 = 	let 	t1 = teller r1
				t2 = teller r2
				n1 = noemer r1
				n2 = noemer r2
				waarde = (t1+t2) % (n1+n2)
				nieuwe = Rationaal waarde
			in Knoop waarde (genereer r1 nieuwe) (genereer nieuwe r2)

vindGetal::Float -> Float -> Rational
vindGetal x y	|x>y = vindGetal y x
		|otherwise = zoek x y stern_brocot

zoek::Float -> Float -> Boom Rational -> Rational
zoek x y (Knoop rat l r)	|(waarde rat)<x = zoek x y r
				|(waarde rat)>y = zoek x y l
				|otherwise = rat 

enc::Rational->String
enc x = zoek_schrijf x stern_brocot

zoek_schrijf::Rational -> Boom Rational -> String
zoek_schrijf x (Knoop rat l r)	|rat<x = "R"++ zoek_schrijf x r
				|rat>x =  "L" ++ zoek_schrijf x l
				|otherwise = ""