49 lines
1.2 KiB
Haskell
49 lines
1.2 KiB
Haskell
-- note that this version of fix uses function recursion in its own definition;
|
|
-- thus its use just means that the recursion has been "pulled" into the "fix" function,
|
|
-- instead of the function that uses it...
|
|
fix :: (a -> a) -> a
|
|
fix f = f (fix f) -- _not_ the {fix f = x where x = f x}
|
|
|
|
fac :: Integer -> Integer
|
|
fac =
|
|
(fix $
|
|
\f n i ->
|
|
if i <= 0 then n
|
|
else f (i * n) (i - 1)) 1
|
|
|
|
fib :: Integer -> Integer
|
|
fib =
|
|
(fix $
|
|
\fnc f s i ->
|
|
if i <= 1 then f
|
|
else case f + s of n -> n `seq` fnc s n (i - 1)) 0 1
|
|
|
|
{--
|
|
-- compute a lazy infinite list. This is
|
|
-- a Y-combinator version of: fibs() = 0:1:zipWith (+) fibs (tail fibs)
|
|
-- which is the same as the above version but easier to read...
|
|
fibs :: () -> [Integer]
|
|
fibs() = fix fibs_
|
|
where
|
|
zipP f (x:xs) (y:ys) =
|
|
case x + y of n -> n `seq` n : f xs ys
|
|
fibs_ a = 0 : 1 : fix zipP a (tail a)
|
|
--}
|
|
|
|
-- easier to read, simpler (faster) version...
|
|
fibs :: () -> [Integer]
|
|
fibs() = 0 : 1 : fix fibs_ 0 1
|
|
where
|
|
fibs_ fnc f s =
|
|
case f + s of n -> n `seq` n : fnc s n
|
|
|
|
-- This code shows how the functions can be used:
|
|
main :: IO ()
|
|
main =
|
|
mapM_
|
|
print
|
|
[ map fac [1 .. 20]
|
|
, map fib [1 .. 20]
|
|
, take 20 fibs()
|
|
]
|