Skip to content

Instantly share code, notes, and snippets.

@alopatindev

alopatindev/fib.hs

Created October 15, 2016 21:11
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save alopatindev/4a4fddb983911c0a7c872e4720014eee to your computer and use it in GitHub Desktop.
Save alopatindev/4a4fddb983911c0a7c872e4720014eee to your computer and use it in GitHub Desktop.
Download ZIP
Fibonacci numbers with Lambda Calculus
Raw
fib.hs
fix :: (a -> a) -> a
fix = \f -> f $ fix f
fib :: Int -> Int
fib = \n -> fix (\f n -> if n <= 2 then 1 else f (n - 2) + f (n - 1)) n
main = putStrLn $ show $ map fib [1..10]
@alopatindev
Copy link
Author

alopatindev commented Oct 15, 2016 •
edited

With Y-Combinator:

$$y := λf.(λx.f (x x)) (λx.f (x x)) fib := y (λf n.if n <= 2 then 1 else f(n - 1) + f(n - 2))$$

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment