Skip to content

Instantly share code, notes, and snippets.

@NightRa
Created October 13, 2015 14:30
Show Gist options
  • Save NightRa/62ac5300b27d027bee52 to your computer and use it in GitHub Desktop.
Save NightRa/62ac5300b27d027bee52 to your computer and use it in GitHub Desktop.
Fibonacci Stream
module Fib where
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Fusion.Stream as S
import qualified Data.Vector.Fusion.Stream.Monadic as SM
import Data.Vector.Fusion.Stream.Size
import Data.Vector.Fusion.Util
{-
euler2 n = sum $ filter even $ takeWhile (<n) $ fibs
How can I write this and fuse into what's below?
-}
fibsStep :: (Int, Int) -> S.Step (Int,Int) Int
fibsStep (a,b) = S.Yield a (b, a + b)
fibs :: S.Stream Int
fibs = SM.Stream (Id . fibsStep) (1,2) Unknown
euler2 :: Int -> Int
euler2 n = S.foldl' (+) 0 $ S.filter even $ S.takeWhile (<n) fibs
{-
Yaay!!!
This compiles to what's below, a tight loop in cpu registers:
-}
{-
euler2 :: Int -> Int
euler2 n = go 0 1 2
where go sum a b = if a < n
then
if even a
then go (sum + a) b (a + b)
else go sum b (a + b)
else sum
-}
main :: IO ()
main = do
t <- readLn
ns <- V.replicateM t readLn
V.forM_ ns $ \n ->
print $ euler2 n
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment