22 Aug 18:38 2013

## instance Alternative ZipList

Stefan Mehner <mehner <at> iai.uni-bonn.de>

2013-08-22 16:38:38 GMT

2013-08-22 16:38:38 GMT

I had an idea for |instance Alternative ZipList|, which doesn't seem to

exist so far. Maybe there just is no need for it. Please tell me what you

think.

After giving the instance definition I will add some intuition on why this

might be useful. Then some words on laws and other conceivable instances.

This appeared on stackoverflow before to make sure it is new

(http://stackoverflow.com/questions/18210765/instance-alternative-ziplist-in-haskell).

J. Abrahamson proposed to move this to the list, so here it is.

The only thing I found so far is by AndrewC on stackoverflow:

There are two sensible choices for Zip [1,3,4] <|> Zip [10,20,30,40]:

Zip [1,3,4] because it's first - consistent with Maybe

Zip [10,20,30,40] because it's longest - consistent with Zip [] being

discarded

(Here Zip is basically ZipList with the known Applicative instance.)

Proposed instance

=================

I think the answer should be Zip [1,3,4,40]. Let's see an instance:

> instance Aternative Zip where

> empty = Zip []

> Zip xs <|> Zip ys = Zip (go xs ys) where

> go [] ys = ys

> go xs [] = xs

> go (x:xs) (_:ys) = x : go xs ys

The only Zip a we can produce without knowing the type argument a is Zip

[] :: Zip a, so there is little choice for empty. If the empty list is the

neutral element of the monoid, we might be tempted to use list

concatenation as the monoid operation. However, go is not (++), since

every time we use one entry of the first argument list, we drop one of the

second. Thus we have a kind of overlay: The left argument list hides the

beginning of the right one (or all of it).

[ 1, 3, 4,40] [10,20,30,40] [ 1, 3, 4] [ 1, 3, 4]

^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

| | | | | | | | | | | | | |

[ 1, 3, 4] | [10,20,30,40] []| | | [ 1, 3, 4]

[10,20,30,40] [ 1, 3, 4] [ 1, 3, 4] []

(use monospace for ascii-art)

For the some/many methods I'd guess

> some (Zip z) = Zip (map repeat z)

> many (Zip z) = Zip (map repeat z ++ repeat [])

where some takes a ziplist and replaces every entry x by repeat x and many

does the same but additionally extends the ziplist with empty lists.

Probably not particularly usefull, but that's what the recursive

definition of some and many gives.

What is it good for?

====================

One intuition behind ziplists is processes: A finite or infinite stream of

results. When zipping, we combine streams, which is reflected by the

Applicative instance. When the end of the list is reached, the stream

doesn't produce further elements. This is where the Alternative instance

comes in handy: We can name a replacement, taking over as soon as the

default process terminates.

For example we could write

< fmap Just foo <|> pure Nothing

to wrap every element of the ziplist foo into a Just and continue with

Nothing afterwards. The resulting ziplist is infinite, reverting to a

default value after all (actual) values have been used up. This could of

course be done by hand by appending an infinite list inside the Zip

constructor. Yet the above is more elegant and does not assume knowledge

of constructors, leading to higher code reusability.

Another intuition one might have of zipLists is partial functions on

naturals. Using this analogy, <|> behaves like the Monoid instance of Map

and IntMap.

Lawfulness

==========

The definition of <|> given above is associative and the empty list really

is the empty element. We also have

< Zip [] <*> xs = fs <*> Zip [] = Zip []

< (fs <|> gs) <*> xs = fs <*> xs <|> gs <*> xs

< fs <*> (xs <|> ys) = fs <*> xs <|> fs <*> ys

so all the laws you could ask for are satisfied (which is not true for

list concatenation by the way).

This instance is consistent with the one for Maybe: Choice is biased to

the left, yet when the left argument is unable to produce a value, the

right argument takes over. The functions

> zipToMaybe :: Zip a -> Maybe a

> zipToMaybe (Zip []) = Nothing

> zipToMaybe (Zip (x:_)) = Just x

> maybeToZip :: Maybe a -> Zip a

> maybeToZip Nothing = Zip []

> maybeToZip (Just x) = pure x

are morphisms of alternatives (meaning psi x <|> psi y = psi (x <|> y) and

psi x <*> psi y = psi (x <*> y)).

Other options

=============

Before putting this up to discussion I have to say this was conceived in

an armchair: Until now I don't really know of any concrete uses for this

instance. Might be there are none.

Some words on AndrewC's instances (none of which has been put forward as a

serious suggestion).

Picking the longer list has a number of problems to it. When it comes to

infinite lists (which are introduced by pure), we get undefined values.

Also it's not very lazy: We have to evaluate both arguments until the

shorter list ends just to get the first entry of the result. When both

lists are of equal length we probably pick the left one, which defies the

laws (distributivity in particular). Finally, you could just write

> maximumBy (compare `on` length) [ys,xs]

which is surprisingly readable (and biassed to the right).

Picking the first nonempty list also feels strange: The 100-th entry of xs

<|> ys should only depend on the 100-th entry of xs and ys or their

absence. This is reasonable since processes shouldn't care to much about

what happend 100 steps earlier. Yet if we only check for empty lists at

the very beginning, the choice is permanent. Again, if you insist on doing

so, just use

> maximumBy (compare `on` not . null) [ys,xs]

The overlaying instance given above introduces some non-trivial behaviour

by allowing to mix lists together (instead of just returning one of the

arguments). I can't think of any way to build this by combining four

existing functions (avoiding length and drop). It satisfies all the laws

and I can image it might at least be of some use.

exist so far. Maybe there just is no need for it. Please tell me what you

think.

After giving the instance definition I will add some intuition on why this

might be useful. Then some words on laws and other conceivable instances.

This appeared on stackoverflow before to make sure it is new

(http://stackoverflow.com/questions/18210765/instance-alternative-ziplist-in-haskell).

J. Abrahamson proposed to move this to the list, so here it is.

The only thing I found so far is by AndrewC on stackoverflow:

There are two sensible choices for Zip [1,3,4] <|> Zip [10,20,30,40]:

Zip [1,3,4] because it's first - consistent with Maybe

Zip [10,20,30,40] because it's longest - consistent with Zip [] being

discarded

(Here Zip is basically ZipList with the known Applicative instance.)

Proposed instance

=================

I think the answer should be Zip [1,3,4,40]. Let's see an instance:

> instance Aternative Zip where

> empty = Zip []

> Zip xs <|> Zip ys = Zip (go xs ys) where

> go [] ys = ys

> go xs [] = xs

> go (x:xs) (_:ys) = x : go xs ys

The only Zip a we can produce without knowing the type argument a is Zip

[] :: Zip a, so there is little choice for empty. If the empty list is the

neutral element of the monoid, we might be tempted to use list

concatenation as the monoid operation. However, go is not (++), since

every time we use one entry of the first argument list, we drop one of the

second. Thus we have a kind of overlay: The left argument list hides the

beginning of the right one (or all of it).

[ 1, 3, 4,40] [10,20,30,40] [ 1, 3, 4] [ 1, 3, 4]

^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

| | | | | | | | | | | | | |

[ 1, 3, 4] | [10,20,30,40] []| | | [ 1, 3, 4]

[10,20,30,40] [ 1, 3, 4] [ 1, 3, 4] []

(use monospace for ascii-art)

For the some/many methods I'd guess

> some (Zip z) = Zip (map repeat z)

> many (Zip z) = Zip (map repeat z ++ repeat [])

where some takes a ziplist and replaces every entry x by repeat x and many

does the same but additionally extends the ziplist with empty lists.

Probably not particularly usefull, but that's what the recursive

definition of some and many gives.

What is it good for?

====================

One intuition behind ziplists is processes: A finite or infinite stream of

results. When zipping, we combine streams, which is reflected by the

Applicative instance. When the end of the list is reached, the stream

doesn't produce further elements. This is where the Alternative instance

comes in handy: We can name a replacement, taking over as soon as the

default process terminates.

For example we could write

< fmap Just foo <|> pure Nothing

to wrap every element of the ziplist foo into a Just and continue with

Nothing afterwards. The resulting ziplist is infinite, reverting to a

default value after all (actual) values have been used up. This could of

course be done by hand by appending an infinite list inside the Zip

constructor. Yet the above is more elegant and does not assume knowledge

of constructors, leading to higher code reusability.

Another intuition one might have of zipLists is partial functions on

naturals. Using this analogy, <|> behaves like the Monoid instance of Map

and IntMap.

Lawfulness

==========

The definition of <|> given above is associative and the empty list really

is the empty element. We also have

< Zip [] <*> xs = fs <*> Zip [] = Zip []

< (fs <|> gs) <*> xs = fs <*> xs <|> gs <*> xs

< fs <*> (xs <|> ys) = fs <*> xs <|> fs <*> ys

so all the laws you could ask for are satisfied (which is not true for

list concatenation by the way).

This instance is consistent with the one for Maybe: Choice is biased to

the left, yet when the left argument is unable to produce a value, the

right argument takes over. The functions

> zipToMaybe :: Zip a -> Maybe a

> zipToMaybe (Zip []) = Nothing

> zipToMaybe (Zip (x:_)) = Just x

> maybeToZip :: Maybe a -> Zip a

> maybeToZip Nothing = Zip []

> maybeToZip (Just x) = pure x

are morphisms of alternatives (meaning psi x <|> psi y = psi (x <|> y) and

psi x <*> psi y = psi (x <*> y)).

Other options

=============

Before putting this up to discussion I have to say this was conceived in

an armchair: Until now I don't really know of any concrete uses for this

instance. Might be there are none.

Some words on AndrewC's instances (none of which has been put forward as a

serious suggestion).

Picking the longer list has a number of problems to it. When it comes to

infinite lists (which are introduced by pure), we get undefined values.

Also it's not very lazy: We have to evaluate both arguments until the

shorter list ends just to get the first entry of the result. When both

lists are of equal length we probably pick the left one, which defies the

laws (distributivity in particular). Finally, you could just write

> maximumBy (compare `on` length) [ys,xs]

which is surprisingly readable (and biassed to the right).

Picking the first nonempty list also feels strange: The 100-th entry of xs

<|> ys should only depend on the 100-th entry of xs and ys or their

absence. This is reasonable since processes shouldn't care to much about

what happend 100 steps earlier. Yet if we only check for empty lists at

the very beginning, the choice is permanent. Again, if you insist on doing

so, just use

> maximumBy (compare `on` not . null) [ys,xs]

The overlaying instance given above introduces some non-trivial behaviour

by allowing to mix lists together (instead of just returning one of the

arguments). I can't think of any way to build this by combining four

existing functions (avoiding length and drop). It satisfies all the laws

and I can image it might at least be of some use.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe