unfoldl -package:stm-containers

unfoldl f x is equivalent to reverse (unfoldr (fmap swap . f) x).

unfoldl f x is equivalent to reverse (unfoldr (fmap swap . f) x).

Linear variant of unfold. Note how they are implemented exactly identically. They could be merged if multiplicity polymorphism was supported.

Construct a Moore machine from a state valuation and transition function

To eveluate function repeatedly to construct a list of type LengthR n a. The function recieve a state and return a new state and an element value.

>>> :set -XDataKinds

>>> unfoldl (\n -> (n + 1, 2 * n)) 0 :: LengthR 5 Integer
((((NilR :+ 8) :+ 6) :+ 4) :+ 2) :+ 0

A projection on data, which only knows how to execute a strict left-fold. It is a monad and a monoid, and is very useful for efficiently aggregating the projections on data intended for left-folding, since its concatenation (<>) has complexity of O(1).

• Intuition

The intuition for this abstraction can be derived from lists. Let's consider the foldl' function for lists:

foldl' :: (b -> a -> b) -> b -> [a] -> b

If we rearrange its parameters we get

foldl' :: [a] -> (b -> a -> b) -> b -> b

Which in Haskell is essentially the same as

foldl' :: [a] -> (forall b. (b -> a -> b) -> b -> b)

We can isolate that part into an abstraction:

newtype Unfoldl a = Unfoldl (forall b. (b -> a -> b) -> b -> b)

Then we get to this simple morphism:

list :: [a] -> Unfoldl a
list list = Unfoldl (\ step init -> foldl' step init list)

We can do the same with say Data.Text.Text:

text :: Text -> Unfoldl Char
text text = Unfoldl (\ step init -> Data.Text.foldl' step init text)

And then we can use those both to concatenate with just an O(1) cost:

abcdef :: Unfoldl Char
abcdef = list ['a', 'b', 'c'] <> text "def"

Please notice that up until this moment no actual data materialization has happened and hence no traversals have appeared. All that we've done is just composed a function, which only specifies which parts of data structures to traverse to perform a left-fold. Only at the moment where the actual folding will happen will we actually traverse the source data. E.g., using the "fold" function:

abcdefLength :: Int
abcdefLength = fold Control.Foldl.length abcdef

Unfold sequentially from the end. There is no way to save the accumulator after unfolding is done, since resulting array is delayed, but it's possible to use unfoldlPrimM to achieve such effect.

Just like iunfoldlPrimM, but do the unfolding with index aware function.

Sequentially unfold an array from the left.

Examples

Create an array with Fibonacci numbers starting at the end while performing and IO action on the accumulator for each element of the array.

>>> import Data.Massiv.Array

>>> unfoldlPrimM_ (Sz1 10) (\a@(f0, f1) -> let fn = f0 + f1 in print a >> return ((f1, fn), f0)) (0, 1) :: IO (Array P Ix1 Int)
(0,1)
(1,1)
(1,2)
(2,3)
(3,5)
(5,8)
(8,13)
(13,21)
(21,34)
(34,55)
Array P Seq (Sz1 10)
[ 34, 21, 13, 8, 5, 3, 2, 1, 1, 0 ]

unfold lexer into a function that returns a stream of (state, token)

Unlift a monadic unfold

Construct a strict Moore machine from a state valuation and transition function

It is like unfoldl. But it use monad as an argument instead of function.

>>> :set -XDataKinds

>>> :module + Data.IORef

>>> r <- newIORef 1

>>> count = readIORef r >>= \n -> n <$ writeIORef r (n + 1)

>>> unfoldlM count :: IO (LengthR 5 Integer)
((((NilR :+ 5) :+ 4) :+ 3) :+ 2) :+ 1

It is like unfoldlM. But it has already prepared values.

>>> :set -XDataKinds

>>> :module + Data.IORef

>>> r <- newIORef 1

>>> count = readIORef r >>= \n -> n <$ writeIORef r (n + 1)

>>> unfoldlMWithBase count (NilR :++ 123 :+ 456) :: IO (LengthR 5 Integer)
((((NilR :+ 3) :+ 2) :+ 1) :+ 123) :+ 456

It is like unfoldl. But it has already prepared values.

>>> :set -XDataKinds

>>> xs = NilR :++ 123 :+ 456 :: RangeR 1 5 Integer

>>> unfoldlWithBase (\n -> (n + 1, 2 * n)) 0 xs :: LengthR 5 Integer
((((NilR :+ 4) :+ 2) :+ 0) :+ 123) :+ 456

It is like unfoldlMax. But it uses a monad instead of function.

>>> :set -XDataKinds

>>> :module + Data.IORef

>>> r <- newIORef 1

>>> count = readIORef r >>= \n -> n * 3 <$ writeIORef r (n + 1)

>>> unfoldlMMax count :: IO (RangeR 3 5 Integer)
((((NilR :++ 15) :++ 12) :+ 9) :+ 6) :+ 3

It is like unfoldlMax. But it uses a monad instead of a function.

>>> :set -XDataKinds

>>> :module + Data.IORef

>>> r <- newIORef 1

>>> count = readIORef r >>= \n -> n * 3 <$ writeIORef r (n + 1)

>>> unfoldlMMin count :: IO (RangeR 3 5 Integer)
((NilR :+ 9) :+ 6) :+ 3

It is like unfoldlRange. But it use a monad instead of a function.

>>> :set -XDataKinds

>>> :module + Data.IORef

>>> r <- newIORef 1

>>> count = readIORef r >>= \n -> n * 3 <$ writeIORef r (n + 1)

>>> unfoldlMRange ((< 5) <$> readIORef r) count :: IO (RangeR 3 5 Integer)
(((NilR :++ 12) :+ 9) :+ 6) :+ 3

It is like unfoldlRangeMaybe. But it use a monad instead of a function. The first argument monad returns a boolean value. It creates values while this boolean value is True. If this boolean value is False before to create enough values or True after to create full values, then unfoldlMRangeMaybe returns Nothing.

>>> :set -XDataKinds

>>> :module + Data.IORef

>>> r <- newIORef 1

>>> check n0 = (< n0) <$> readIORef r

>>> count = readIORef r >>= \n -> n * 3 <$ writeIORef r (n + 1)

>>> unfoldlMRangeMaybe (check 2) count :: IO (Maybe (RangeR 3 5 Integer))
Nothing

>>> writeIORef r 1

>>> unfoldlMRangeMaybe (check 5) count :: IO (Maybe (RangeR 3 5 Integer))
Just ((((NilR :++ 12) :+ 9) :+ 6) :+ 3)

>>> writeIORef r 1

>>> unfoldlMRangeMaybe (check 10) count :: IO (Maybe (RangeR 3 5 Integer))
Nothing

It is like unfoldrMRangeMaybe. But it has already prepared values.

>>> :set -XDataKinds

>>> :module + Data.IORef

>>> r <- newIORef 1

>>> check = (< 3) <$> readIORef r

>>> count = readIORef r >>= \n -> n * 3 <$ writeIORef r (n + 1)

>>> xs = NilR :++ 123 :+ 456 :: RangeR 1 5 Integer

>>> :{
unfoldlMRangeMaybeWithBase check count xs
:: IO (Maybe (RangeR 3 5 Integer))
:}
Just ((((NilR :++ 6) :+ 3) :+ 123) :+ 456)

It is like unfoldlMRange. But it has already prepared values.

>>> :set -XDataKinds

>>> :module + Data.IORef

>>> r <- newIORef 1

>>> count = readIORef r >>= \n -> n * 3 <$ writeIORef r (n + 1)

>>> xs = NilR :++ 123 :+ 456 :: RangeR 1 5 Integer

>>> :{
unfoldlMRangeWithBase ((< 3) <$> readIORef r) count xs
:: IO (RangeR 3 5 Integer)
:}
(((NilR :++ 6) :+ 3) :+ 123) :+ 456

To eveluate a function to construct values maximum number of times. The function recieves a state and return a value and a new state.

>>> :set -XDataKinds

>>> unfoldlMax (\n -> (n + 1, n * 3)) 1 :: RangeR 3 5 Integer
((((NilR :++ 15) :++ 12) :+ 9) :+ 6) :+ 3