[GHC] #13520: instance Alternative ZipList
#13520: instance Alternative ZipList -------------------------------------+------------------------------------- Reporter: Iceland_jack | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: | Version: 8.0.1 libraries/base | Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- The paper "From monoids to near-semirings: the essence of MonadPlus and Alternative`" mentions
Perhaps surprisingly, `ZipList`s have an `Alternative` instance. Like the `Alternative` instance for `Maybe`, the one for `ZipList` has a left bias.
{{{#!hs instance Alternative ZipList where empty :: ZipList a empty = ZL []
(<|>) :: ZipList a -> ZipList a -> ZipList a ZL xs <|> ZL ys = ZL (xs ++ drop (length xs) ys) }}}
Has this been considered for base? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13520 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13520: instance Alternative ZipList -------------------------------------+------------------------------------- Reporter: Iceland_jack | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by Iceland_jack): * type: bug => feature request Old description:
The paper "From monoids to near-semirings: the essence of MonadPlus and Alternative`" mentions
Perhaps surprisingly, `ZipList`s have an `Alternative` instance. Like the `Alternative` instance for `Maybe`, the one for `ZipList` has a left bias.
{{{#!hs instance Alternative ZipList where empty :: ZipList a empty = ZL []
(<|>) :: ZipList a -> ZipList a -> ZipList a ZL xs <|> ZL ys = ZL (xs ++ drop (length xs) ys) }}}
Has this been considered for base?
New description: The paper "From monoids to near-semirings: the essence of `MonadPlus` and `Alternative`" mentions
Perhaps surprisingly, `ZipList`s have an `Alternative` instance. Like the `Alternative` instance for `Maybe`, the one for `ZipList` has a left bias.
{{{#!hs instance Alternative ZipList where empty :: ZipList a empty = ZL []
(<|>) :: ZipList a -> ZipList a -> ZipList a ZL xs <|> ZL ys = ZL (xs ++ drop (length xs) ys) }}}
Has this been considered for base? -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13520#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13520: instance Alternative ZipList -------------------------------------+------------------------------------- Reporter: Iceland_jack | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by Iceland_jack: Old description:
The paper "From monoids to near-semirings: the essence of `MonadPlus` and `Alternative`" mentions
Perhaps surprisingly, `ZipList`s have an `Alternative` instance. Like the `Alternative` instance for `Maybe`, the one for `ZipList` has a left bias.
{{{#!hs instance Alternative ZipList where empty :: ZipList a empty = ZL []
(<|>) :: ZipList a -> ZipList a -> ZipList a ZL xs <|> ZL ys = ZL (xs ++ drop (length xs) ys) }}}
Has this been considered for base?
New description: The paper "From monoids to near-semirings: the essence of `MonadPlus` and `Alternative`" mentions
Perhaps surprisingly, `ZipList`s have an `Alternative` instance. Like the `Alternative` instance for `Maybe`, the one for `ZipList` has a left bias.
{{{#!hs instance Alternative ZipList where empty :: ZipList a empty = ZL []
(<|>) :: ZipList a -> ZipList a -> ZipList a ZL xs <|> ZL ys = ZL (xs ++ drop (length xs) ys) }}}
Has this been considered for base? -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13520#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13520: instance Alternative ZipList -------------------------------------+------------------------------------- Reporter: Iceland_jack | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by Iceland_jack: Old description:
The paper "From monoids to near-semirings: the essence of `MonadPlus` and `Alternative`" mentions
Perhaps surprisingly, `ZipList`s have an `Alternative` instance. Like the `Alternative` instance for `Maybe`, the one for `ZipList` has a left bias.
{{{#!hs instance Alternative ZipList where empty :: ZipList a empty = ZL []
(<|>) :: ZipList a -> ZipList a -> ZipList a ZL xs <|> ZL ys = ZL (xs ++ drop (length xs) ys) }}}
Has this been considered for base?
New description: The paper "From monoids to near-semirings: the essence of `MonadPlus` and `Alternative`" mentions
Perhaps surprisingly, `ZipList`s have an `Alternative` instance. Like the `Alternative` instance for `Maybe`, the one for `ZipList` has a left bias.
{{{#!hs instance Alternative ZipList where empty :: ZipList a empty = ZL []
(<|>) :: ZipList a -> ZipList a -> ZipList a ZL xs <|> ZL ys = ZL (xs ++ drop (length xs) ys) }}}
Has this been considered for base? -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13520#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13520: instance Alternative ZipList -------------------------------------+------------------------------------- Reporter: Iceland_jack | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.0.1 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * keywords: => newcomer Comment: Indeed it has! See https://mail.haskell.org/pipermail/libraries/2015-July/025975.html, where it garnered a general consensus of support. Now all we need is someone to submit the patch which implements this. Will you be the one? :) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13520#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13520: instance Alternative ZipList -------------------------------------+------------------------------------- Reporter: Iceland_jack | Owner: (none) Type: feature request | Status: patch Priority: normal | Milestone: Component: libraries/base | Version: 8.0.1 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D3416 Wiki Page: | -------------------------------------+------------------------------------- Changes (by ehubinette): * status: new => patch * differential: => Phab:D3416 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13520#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13520: instance Alternative ZipList
-------------------------------------+-------------------------------------
Reporter: Iceland_jack | Owner: (none)
Type: feature request | Status: patch
Priority: normal | Milestone:
Component: libraries/base | Version: 8.0.1
Resolution: | Keywords: newcomer
Operating System: Unknown/Multiple | Architecture:
| Unknown/Multiple
Type of failure: None/Unknown | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s): Phab:D3416
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by Ben Gamari
#13520: instance Alternative ZipList -------------------------------------+------------------------------------- Reporter: Iceland_jack | Owner: (none) Type: feature request | Status: closed Priority: normal | Milestone: 8.4.1 Component: libraries/base | Version: 8.0.1 Resolution: fixed | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D3416 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: patch => closed * resolution: => fixed * milestone: => 8.4.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13520#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13520: instance Alternative ZipList -------------------------------------+------------------------------------- Reporter: Iceland_jack | Owner: (none) Type: feature request | Status: closed Priority: normal | Milestone: 8.4.1 Component: libraries/base | Version: 8.0.1 Resolution: fixed | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D3416 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Iceland_jack): Cale from `#haskell` points out the following: {{{ <Cale> Iceland_jack: I think it probably ought to be the one which uses Semigroup's (<>) to combine corresponding elements. <Cale> Iceland_jack: Then you can recover the instance there by using the First semigroup }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13520#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13520: instance Alternative ZipList -------------------------------------+------------------------------------- Reporter: Iceland_jack | Owner: (none) Type: feature request | Status: closed Priority: normal | Milestone: 8.4.1 Component: libraries/base | Version: 8.0.1 Resolution: fixed | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D3416 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Zemyla): The instance for `(<|>)` would probably be more efficient as: {{{ #!haskell ZipList xs <|> ZipList ys = ZipList $ go (0 :: Int) xs where go n _ | n `seq` False = undefined go n [] = drop n ys go n (x:xs) = x:go (n + 1) xs }}} This way, it only has to iterate over xs once. Or, you could do it in `build`/`foldr` style: {{{ #!haskell ZipList xs <|> ZipList ys = ZipList (build $ zipListPlusBF xs ys) zipListPlusBF :: [a] -> [a] -> (a -> b -> b) -> b -> b zipListPlusBF xs ys c z = foldr goX endX xs 0# where goX x r n# = c x $ r (n# +# 1#) endX n# = foldr goY endY ys n# goY y r n# | isTrue# (n# ># 0#) = r (n# -# 1#) | otherwise = c y $ r 0# endY _ = z }}} This would have the advantage that it should ideally realize, for instance, that pure x <|> anything = pure x, or at the very least doesn't reference the right-hand side at all. We could probably use both and switch between them with `RULES` like is done for most of the algorithms in `Data.List`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13520#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13520: instance Alternative ZipList -------------------------------------+------------------------------------- Reporter: Iceland_jack | Owner: (none) Type: feature request | Status: closed Priority: normal | Milestone: 8.4.1 Component: libraries/base | Version: 8.0.1 Resolution: fixed | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D3416, Wiki Page: | Phab:D4638 -------------------------------------+------------------------------------- Changes (by dfeuer): * differential: Phab:D3416 => Phab:D3416, Phab:D4638 Comment: Zemyla, in an amazing coincidence of timing, I happened to write something very similar to your first instance in Phab:D4638 just now. I think it makes sense to use `foldr` to fold over the first argument. Unfortunately, the `build` is a bit trickier, because it will end up copying the second list if it doesn't fuse away. I'm not sure if it's possible to work around that issue with `RULES`. Appends are generally handled by `augment`, but that mechanism isn't powerful enough for what we're doing here because it leaves no room to use an accumulated count in the tail. As for the hand- unboxing, I'd only go for that if GHC proves incapable of unboxing on its own; it's really quite good at that most of the time. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13520#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13520: instance Alternative ZipList -------------------------------------+------------------------------------- Reporter: Iceland_jack | Owner: (none) Type: feature request | Status: closed Priority: normal | Milestone: 8.4.1 Component: libraries/base | Version: 8.0.1 Resolution: fixed | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D3416, Wiki Page: | Phab:D4638 -------------------------------------+------------------------------------- Changes (by dfeuer): * cc: dfeuer (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13520#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC