This paper on monoids and near-semirings gives an Alternative instance

for ZipList consistent with its Applicative instance:

https://lirias.kuleuven.be/bitstream/123456789/499951/1/main.pdfThe original definition of (<|>) leaves a lot to be desired, because

it iterates through the first list twice, preventing inlining of xs:

ZipList xs <|> ZipList ys = ZipList $ xs ++ drop (length xs) ys

Edited for efficiency, it winds up being:

instance Alternative ZipList where

empty = ZipList []

ZipList xs <|> ZipList ys = ZipList $ go xs ys where

go [] ys = ys

go xs [] = xs

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

A different formulation, using foldr/build, goes like this:

ZipList xs <|> ZipList ys = ZipList $ build $ \c z -> let

goX x xr !n = c x $ xr $ n + 1

goY y yr n

| n <= 0 = c y $ yr 0

| otherwise = yr $ n - 1

in foldr goX (foldr goY (const z) ys) ys (0 :: Int)

It is an idempotent monoid, and sconcat/mconcat can be written as follows:

zlconcat :: Foldable t => t (ZipList a) -> ZipList a

zlconcat xss = ZipList $ build $ \c z -> let

goO (ZipList xs) xr !n = foldr goI endI xs 0 where

goI x xk i

| i < n = xk $ i + 1

| otherwise = c x $ xk $ i + 1

endI i = if i < n then xr n else xr i

in foldr goO (const z) xss (0 :: Int)

So in the end, the Semigroup/Monoid instances look like:

instance Semigroup (ZipList a) where

(<>) = (<|>)

sconcat = zlconcat

stimes = stimesIdempotentMonoid

instance Monoid (ZipList a) where

mempty = empty

mappend = (<|>)

mconcat = zlconcat

Sadly, the paper doesn't prove that it's a valid left catch

Alternative, and sort of mentions it offhand, but tests suggest it is

associative, [] is obviously the identity for <|> and the zero for

<*>, and pure a <|> x = pure a.

Any ideas on which implementation to prefer, or different ideas for

implementing sconcat/mconcat?

_______________________________________________

Libraries mailing list

[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries