Combining stream and list fusion

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Combining stream and list fusion

Bas van Dijk-2
Hello,

I'm trying to make the following faster:

Data.Vector.Generic.fromList list

where 'list' is some expression yielding a list.

(For example: map (+1) $ map (*2) [1..1000000])

Note that Data.Vector.Generic.fromList is defined as:

fromList :: Vector v a => [a] -> v a
{-# INLINE fromList #-}
fromList = unstream . Stream.fromList

where Stream.fromList is defined in Data.Vector.Fusion.Stream as:

fromList :: [a] -> Stream a
{-# INLINE fromList #-}
fromList = M.fromList

where M.fromList is defined in Data.Vector.Fusion.Stream.Monadic as:

fromList :: Monad m => [a] -> Stream m a
{-# INLINE fromList #-}
fromList xs = unsafeFromList Unknown xs

where unsafeFromList is defined as:

unsafeFromList :: Monad m => Size -> [a] -> Stream m a
{-# INLINE_STREAM unsafeFromList #-}
unsafeFromList sz xs = Stream step xs sz
  where
    step (x:xs) = return (Yield x xs)
    step []     = return Done

I would like to fuse the construction of the list with the
construction of the stream as in:

import GHC.Base ( build )

 {-# RULES
"unsafeFromList/build"
  forall sz (g :: forall b. (a -> b -> b) -> b -> b).
  unsafeFromList sz (build g) = unsafeFromListF sz g
  #-}

unsafeFromListF :: forall m a. Monad m
                => Size
                -> (forall b. (a -> b -> b) -> b -> b)
                -> Stream m a
{-# INLINE unsafeFromListF #-}
unsafeFromListF sz g = Stream step st sz
    where
      St step st = g c z

      c :: a -> St m a -> St m a
      c x st = St (\(St s st') -> s st')
                  (St (\s -> return (Yield x s)) st)

      z :: St m a
      z = St (\_ -> return Done) undefined -- Ouch!

data St m a = St ((St m a) -> m (Step (St m a) a)) (St m a)

Unfortunately, some initial experiments show that this doesn't make it
faster. Are there ways to improve this? (Bonus points for getting rid
of the undefined!)

Regards,

Bas

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Combining stream and list fusion

Roman Leshchinskiy
Bas van Dijk wrote:
> Hello,
>
> I'm trying to make the following faster:
>
> Data.Vector.Generic.fromList list
>
> where 'list' is some expression yielding a list.

Unfortunately, I don't think that's possible. The problem is that you
'list' will be expressed in terms of foldr/build and fromList would have
to produce a Stream, i.e., basically an unfoldr. But AFAIK, there is no
unfoldr/build fusion rule. There is one the other way round and vector
makes use of that in toList.

Roman




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe