Created
October 13, 2015 14:30
-
-
Save NightRa/62ac5300b27d027bee52 to your computer and use it in GitHub Desktop.
Fibonacci Stream
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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