Skip to content

Instantly share code, notes, and snippets.

@hiroshi-maybe
Created April 28, 2013 22:23
Show Gist options
  • Select an option

  • Save hiroshi-maybe/5478661 to your computer and use it in GitHub Desktop.

Select an option

Save hiroshi-maybe/5478661 to your computer and use it in GitHub Desktop.
import Control.Monad.Fix
------------------------------------------------
-- fact
-- fact is a fixpoint for lambda_fact
fact n = if n == 0 then 1 else n * fact (n-1)
lambda_fact = (\g n -> if n == 0 then 1 else n * g (n-1))
-- fixpoint combinator 'fix' "encode" recursion of fact
fixpoint_fact = fix lambda_fact
------------------------------------------------
-- filter
filter' f xs = if null xs then []
else let x = if f (head xs) then [head xs] else []
in x++ (filter' f $ tail xs)
lambda_filter = (\g f xs -> if null xs then []
else let x = if f (head xs) then [head xs] else []
in x++ (g f $ tail xs))
fixpoint_filter = fix lambda_filter
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment