Stream acceleration, data type

Question

I created a type that should emulate a "stream". This is basically a memoryless list.

data Stream a = forall s. Stream (s -> Maybe (a, s)) s

Basically, a stream has two elements. A state sand a function that takes state and returns a type element aand a new state.

I want to be able to perform operations on threads, so I imported Data.Foldableand defined the threads on it as such:

import Data.Foldable

instance Foldable Stream where
  foldr k z (Stream sf s) = go (sf s)
    where
      go Nothing = z
      go (Just (e, ns)) = e `k` go (sf ns)

To check my flow rate, I defined the following function:

mysum = foldl' (+) 0

And now we can compare the speed of regular lists and the type of my stream:

x1 = [1..n]
x2 = Stream (\s -> if (s == n + 1) then Nothing else Just (s, s + 1)) 1

--main = print $ mysum x1
--main = print $ mysum x2

My streams are about half the speed of lists (full code here ).

Also, here is the best situation, with no list or thread:

bestcase :: Int
bestcase = go 1 0 where
  go i c = if i == n then c + i else go (i+1) (c+i)

This is much faster than the list and stream versions.

So, I have two questions:

• , , , .
• bestcase.

Answer 1

foldl', Foldable, foldr, . -

foldl' :: (b -> a -> b) -> b -> t a -> b
foldl' f z0 xs = foldr f' id xs z0
  where f' x k z = k $! f z x

foldl '- ; , Foldable foldl' , .

 foldl' op acc0 (Stream sf s0) = loop s0 acc0
   where 
    loop !s !acc = case sf s  of 
      Nothing -> acc
      Just (a,s') -> loop s' (op acc a)

, bestcase , , . vector https://hackage.haskell.org/package/vector-0.10.12.2/docs/src/Data-Vector-Fusion-Stream.html ; "fusion" https://github.com/bos/text/blob/master/Data/Text/Internal/Fusion.