Generate is a library for lazy list manipulation.
Generators are lists whose transformations are applied lazily as items are requested. This makes is so that expressions like:
import Generate as G
G.fromList [1, 2, 3]
|> G.map ((+) 1)
|> G.filter (\x -> x % 2 == 0)
|> G.map toString
|> G.toList
Only end up iterating through the list once while still providing the same results as their List module counterparts.
Construct a Generator from a single value.
> singleton 1
Generator { items = [1], transform = <function> }
: Generate.Generator number number
Construct a Generator from a List.
> fromList [1, 2, 3]
Generator { items = [1,2,3], transform = <function> }
: Generate.Generator number number
Construct a List from a Generator.
> fromList [1, 2, 3] |> toList
[1, 2, 3] : List number
Get the next element in the generator after transforming it.
> fromList [1, 2, 3] |> filter ((/=) 1) |> next
(Just 2, Generator { items = [3], transform = <function> })
: ( Maybe.Maybe number, Generate.Generator number number )
> fromList [1, 2, 3] |> filter ((==) 5) |> next
(Nothing, Generator { items = [], transform = <function> })
: ( Maybe.Maybe number, Generate.Generator number number )
Transform the elements of a Generator.
> fromList [1, 2, 3] |> map ((+) 1) |> toList
[2, 3, 4] : List number
Filter the elements of a Generator.
> fromList [1, 2, 3] |> filter (flip (>) 1) |> toList
[2, 3] : List number
Remove elements that match the given predicate from the Generator.
> fromList [1, 2, 3] |> remove (\x -> x % 2 == 0) |> toList
[1, 3] : List number
Reverse a Generator's elements.
Take the first n
elements from a Generator.
> fromList [1, 2, 3] |> take 1 |> toList
[1] : List number
Note: This function is applied to the original list:
> fromList [1, 2, 3] |> filter ((/=) 1) |> take 1 |> toList
[] : List number
Drop the first n
elements from a Generator.
> fromList [1, 2, 3] |> drop 1 |> toList
[2, 3] : List number
Note: This function is applied to the original list:
> fromList [1, 2, 3] |> filter ((/=) 1) |> drop 1 |> toList
[2, 3] : List number
Fold a Generator from the left.
> fromList [1, 2, 3] |> foldl (::) []
[3, 2, 1] : List number
Fold a Generator from the right.
> fromList [1, 2, 3] |> foldr (::) []
[1, 2, 3] : List number
Determine if any of the Generator's elements match the predicate.
> fromList [1, 2, 3] |> any (\x -> x % 2 == 0)
True : Bool
> fromList [1, 3, 5] |> any (\x -> x % 2 == 0)
False : Bool
Determine if all of the Generator's elements match the predicate.
> fromList [2, 4, 6] |> all (\x -> x % 2 == 0)
True : Bool
> fromList [1, 2, 3] |> all (\x -> x % 2 == 0)
False : Bool
Compute the product of the Generator's elements.
> fromList [1, 2, 3] |> sum
6 : number
Compute the product of the Generator's elements.
> fromList [1, 2, 3] |> product
6 : number
Compute the length of a Generator.
> fromList [1, 2, 3] |> length
3 : Int
module Generate ( Generator
, singleton, fromList, toList, next
, map, filter, remove, reverse, take, drop
, foldl, foldr, any, all, sum, product, length
) where
{-| Generate is a library for lazy list manipulation.
# Types
@docs Generator
## Converting to and from Generators
@docs singleton, fromList, toList
## Extracting values
@docs next
## Transforming Generators
@docs map, filter, remove, reverse, take, drop
## Producing values
@docs foldl, foldr, any, all, sum, product, length
-}
{-| Generators are lists whose transformations are applied lazily as
items are requested. This makes is so that expressions like:
import Generate as G
G.fromList [1, 2, 3]
|> G.map ((+) 1)
|> G.filter (\x -> x % 2 == 0)
|> G.map toString
|> G.toList
Only end up iterating through the list once while still providing the
same results as their List module counterparts.
-}
type Generator a b
= Generator { items : List a
, transform : a -> Mutator b
}
type Mutator a
= Keep a
| Skip
unwrap gen =
case gen of
Generator gen ->
gen
mapMutator : (a -> b) -> Mutator a -> Mutator b
mapMutator f m =
case m of
Skip ->
Skip
Keep x ->
Keep (f x)
filterMutator : (a -> Bool) -> Mutator a -> Mutator a
filterMutator f m =
case m of
Skip ->
Skip
Keep x ->
if f x then
Keep x
else
Skip
{-| Construct a Generator from a single value.
> singleton 1
Generator { items = [1], transform = <function> }
: Generate.Generator number number
-}
singleton : a -> Generator a a
singleton a =
Generator { items = [a], transform = Keep }
{-| Construct a Generator from a List.
> fromList [1, 2, 3]
Generator { items = [1,2,3], transform = <function> }
: Generate.Generator number number
-}
fromList : List a -> Generator a a
fromList xs =
Generator { items = xs, transform = Keep }
{-| Construct a List from a Generator.
> fromList [1, 2, 3] |> toList
[1, 2, 3] : List number
-}
toList : Generator a b -> List b
toList =
List.reverse << foldl (::) []
{-| Get the next element in the generator after transforming it.
> fromList [1, 2, 3] |> filter ((/=) 1) |> next
(Just 2, Generator { items = [3], transform = <function> })
: ( Maybe.Maybe number, Generate.Generator number number )
> fromList [1, 2, 3] |> filter ((==) 5) |> next
(Nothing, Generator { items = [], transform = <function> })
: ( Maybe.Maybe number, Generate.Generator number number )
-}
next : Generator a b -> (Maybe b, Generator a b)
next gen =
let gen' = unwrap gen in
case gen'.items of
[] ->
(Nothing, gen)
(x::xs) ->
case gen'.transform x of
Skip ->
next <| Generator { gen' | items = xs }
Keep a ->
(Just a, Generator { items = xs, transform = gen'.transform })
{-| Transform the elements of a Generator.
> fromList [1, 2, 3] |> map ((+) 1) |> toList
[2, 3, 4] : List number
-}
map : (b -> c) -> Generator a b -> Generator a c
map f gen =
let gen' = unwrap gen in
Generator { gen' | transform = gen'.transform >> mapMutator f }
{-| Filter the elements of a Generator.
> fromList [1, 2, 3] |> filter (flip (>) 1) |> toList
[2, 3] : List number
-}
filter : (b -> Bool) -> Generator a b -> Generator a b
filter f gen =
let gen' = unwrap gen in
Generator { gen' | transform = gen'.transform >> filterMutator f }
{-| Remove elements that match the given predicate from the Generator.
> fromList [1, 2, 3] |> remove (\x -> x % 2 == 0) |> toList
[1, 3] : List number
-}
remove : (b -> Bool) -> Generator a b -> Generator a b
remove f = filter (not << f)
{-| Reverse a Generator's elements. -}
reverse : Generator a b -> Generator a b
reverse gen =
let gen' = unwrap gen in
Generator { gen' | items = List.reverse gen'.items }
{-| Take the first `n` elements from a Generator.
> fromList [1, 2, 3] |> take 1 |> toList
[1] : List number
*Note*: This function is applied to the *original* list:
> fromList [1, 2, 3] |> filter ((/=) 1) |> take 1 |> toList
[] : List number
-}
take : Int -> Generator a b -> Generator a b
take n gen =
let gen' = unwrap gen in
Generator { gen' | items = List.take n gen'.items }
{-| Drop the first `n` elements from a Generator.
> fromList [1, 2, 3] |> drop 1 |> toList
[2, 3] : List number
*Note*: This function is applied to the *original* list:
> fromList [1, 2, 3] |> filter ((/=) 1) |> drop 1 |> toList
[2, 3] : List number
-}
drop : Int -> Generator a b -> Generator a b
drop n gen =
let gen' = unwrap gen in
Generator { gen' | items = List.drop n gen'.items }
{-| Fold a Generator from the left.
> fromList [1, 2, 3] |> foldl (::) []
[3, 2, 1] : List number
-}
foldl : (b -> c -> c) -> c -> Generator a b -> c
foldl f e gen =
let
go gen acc =
case next gen of
(Nothing, _) ->
acc
(Just x, gen) ->
go gen (f x acc)
in
go gen e
{-| Fold a Generator from the right.
> fromList [1, 2, 3] |> foldr (::) []
[1, 2, 3] : List number
-}
foldr : (b -> c -> c) -> c -> Generator a b -> c
foldr f e gen =
let
go gen =
case next gen of
(Nothing, _) ->
e
(Just x, gen) ->
f x (go gen)
in
go gen
{-| Determine if all of the Generator's elements match the predicate.
> fromList [2, 4, 6] |> all (\x -> x % 2 == 0)
True : Bool
> fromList [1, 2, 3] |> all (\x -> x % 2 == 0)
False : Bool
-}
all : (a -> Bool) -> Generator x a -> Bool
all f gen =
case next gen of
(Nothing, _) ->
True
(Just x, gen) ->
if f x then -- The && version of this does not TCO
all f gen
else
False
{-| Determine if any of the Generator's elements match the predicate.
> fromList [1, 2, 3] |> any (\x -> x % 2 == 0)
True : Bool
> fromList [1, 3, 5] |> any (\x -> x % 2 == 0)
False : Bool
-}
any : (a -> Bool) -> Generator x a -> Bool
any f gen =
case next gen of
(Nothing, _) ->
False
(Just x, gen) ->
if f x then -- The || version of this does not TCO
True
else
any f gen
{-| Compute the product of the Generator's elements.
> fromList [1, 2, 3] |> sum
6 : number
-}
sum : Generator a number -> number
sum gen =
foldl (+) 0 gen
{-| Compute the product of the Generator's elements.
> fromList [1, 2, 3] |> product
6 : number
-}
product : Generator a number -> number
product gen =
foldl (*) 1 gen
{-| Compute the length of a Generator.
> fromList [1, 2, 3] |> length
3 : Int
-}
length : Generator a b -> Int
length gen =
foldl ((+) << (always 1)) 0 gen