Skip to content

Instantly share code, notes, and snippets.

@giuliohome
Created December 29, 2017 14:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save giuliohome/b655f8dbb63f53f137877f5a1570afc0 to your computer and use it in GitHub Desktop.
Save giuliohome/b655f8dbb63f53f137877f5a1570afc0 to your computer and use it in GitHub Desktop.
Applying f-algebras to primes
{-# LANGUAGE DeriveFunctor #-}
-- https://bartoszmilewski.com/2017/02/28/f-algebras/
newtype Fix f = Fix (f (Fix f))
unFix :: Fix f -> f (Fix f)
unFix (Fix x) = x
cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix
ana :: Functor f => (a -> f a) -> a -> Fix f
ana coalg = Fix . fmap (ana coalg) . coalg
data StreamF e a = StreamF e a
deriving Functor
data Stream e = Stream e (Stream e)
era :: [Int] -> StreamF Int [Int]
era (p : ns) = StreamF p (filter (notdiv p) ns)
where notdiv p n = n `mod` p /= 0
primes = ana era [2..]
toListC :: Fix (StreamF e) -> [e]
toListC = cata al
where al :: StreamF e [e] -> [e]
al (StreamF e a) = e : a
-- run it online from https://repl.it/repls/FeistyActualBrownbutterfly
main = do
print $ take 5 $ toListC primes -- [2,3,5,7,11]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment