Behavior of groupBy

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Behavior of groupBy

Hans van Thiel
Hello All,

The standard function groupBy of List.hs doesn't work as I expect in
this case:

groupBy (\x y -> (last x) == (last y)) ["abc", "bd","cac"]

results in:

[["abc"],["bd"],["cac"]]

where I want:

[["abc","cac"], ["bd"]]

Am I doing something wrong, or is this a bug? The function is defined
(in List.hs in the hugs Data library) as :

-- | The 'groupBy' function is the non-overloaded version of 'group'.
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  [] =  []
groupBy eq (x:xs) =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs


Thanks,

Hans van Thiel


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Behavior of groupBy

Stefan O'Rear
On Sat, Apr 28, 2007 at 03:49:44PM +0200, Hans van Thiel wrote:

> Hello All,
>
> The standard function groupBy of List.hs doesn't work as I expect in
> this case:
>
> groupBy (\x y -> (last x) == (last y)) ["abc", "bd","cac"]
>
> results in:
>
> [["abc"],["bd"],["cac"]]
>
> where I want:
>
> [["abc","cac"], ["bd"]]
>
> Am I doing something wrong, or is this a bug? The function is defined
> (in List.hs in the hugs Data library) as :
>
> -- | The 'groupBy' function is the non-overloaded version of 'group'.
> groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
> groupBy _  [] =  []
> groupBy eq (x:xs) =  (x:ys) : groupBy eq zs
>                            where (ys,zs) = span (eq x) xs

You are doing something wrong.  groupBy is specified to never reorder
elements.  You probably want to use sortBy first.

Stefan
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Behavior of groupBy

Neil Mitchell
Hi Hans,

> > The standard function groupBy of List.hs doesn't work as I expect in
> > this case:
> >
> > groupBy (\x y -> (last x) == (last y)) ["abc", "bd","cac"]
>
> You are doing something wrong.  groupBy is specified to never reorder
> elements.  You probably want to use sortBy first.

I have a defined groupSetBy which does groupBy working as though the
list was in fact a set (which is often what it really is). Its a
common thing to want - perhaps it should be a library function.

Thanks

Neil
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Behavior of groupBy

Hans van Thiel
In reply to this post by Stefan O'Rear
On Sat, 2007-04-28 at 06:45 -0700, Stefan O'Rear wrote:

> On Sat, Apr 28, 2007 at 03:49:44PM +0200, Hans van Thiel wrote:
> > Hello All,
> >
> > The standard function groupBy of List.hs doesn't work as I expect in
> > this case:
> >
> > groupBy (\x y -> (last x) == (last y)) ["abc", "bd","cac"]
> >
> > results in:
> >
> > [["abc"],["bd"],["cac"]]
> >
> > where I want:
> >
> > [["abc","cac"], ["bd"]]
> >
> > Am I doing something wrong, or is this a bug? The function is defined
> > (in List.hs in the hugs Data library) as :
> >
> > -- | The 'groupBy' function is the non-overloaded version of 'group'.
> > groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
> > groupBy _  [] =  []
> > groupBy eq (x:xs) =  (x:ys) : groupBy eq zs
> >                            where (ys,zs) = span (eq x) xs
>
> You are doing something wrong.  groupBy is specified to never reorder
> elements.  You probably want to use sortBy first.
>
> Stefan
Ah, many thanks...

Hans


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Behavior of groupBy

Hans van Thiel
In reply to this post by Neil Mitchell
On Sat, 2007-04-28 at 15:08 +0100, Neil Mitchell wrote:

> Hi Hans,
>
> > > The standard function groupBy of List.hs doesn't work as I expect in
> > > this case:
> > >
> > > groupBy (\x y -> (last x) == (last y)) ["abc", "bd","cac"]
> >
> > You are doing something wrong.  groupBy is specified to never reorder
> > elements.  You probably want to use sortBy first.
>
> I have a defined groupSetBy which does groupBy working as though the
> list was in fact a set (which is often what it really is). Its a
> common thing to want - perhaps it should be a library function.
And thanks again. I'll roll my own then..

Hans
>
> Thanks
>
> Neil

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Behavior of groupBy

Henning Thielemann
In reply to this post by Hans van Thiel

On Sat, 28 Apr 2007, Hans van Thiel wrote:

> Hello All,
>
> The standard function groupBy of List.hs doesn't work as I expect in
> this case:
>
> groupBy (\x y -> (last x) == (last y)) ["abc", "bd","cac"]
>
> results in:
>
> [["abc"],["bd"],["cac"]]
>
> where I want:
>
> [["abc","cac"], ["bd"]]

I think you must roll your own one. How about repeated 'partition' to
extract all elements that have the same trailing character like the head
word of the list?

I have done this in a more complex setting and called it 'slice':
  http://darcs.haskell.org/haskore/src/Haskore/Basic/TimeOrderedList.lhs


> slice :: (Eq a, Num time) =>
>    (body -> a) -> T time body -> [(a, T time body)]
> slice f perf =
>   let splitByHeadKey pf =
>          fmap
>             (\ev ->
>                let i = f (eventBody ev)
>                    (pf0, pf1) = partition ((i==) . f) 0 0 pf
>                in  ((i,pf0), pf1))
>             (listToMaybe pf)
>   in  List.unfoldr splitByHeadKey perf

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Behavior of groupBy

Hans van Thiel
Thanks for the help! Strangely, I just now received your messages from
April 28, hence the late reply...

Hans van Thiel
On Sat, 2007-04-28 at 18:09 +0200, Henning Thielemann wrote:

> On Sat, 28 Apr 2007, Hans van Thiel wrote:
>
> > Hello All,
> >
> > The standard function groupBy of List.hs doesn't work as I expect in
> > this case:
> >
> > groupBy (\x y -> (last x) == (last y)) ["abc", "bd","cac"]
> >
> > results in:
> >
> > [["abc"],["bd"],["cac"]]
> >
> > where I want:
> >
> > [["abc","cac"], ["bd"]]
>
> I think you must roll your own one. How about repeated 'partition' to
> extract all elements that have the same trailing character like the head
> word of the list?
>
> I have done this in a more complex setting and called it 'slice':
>   http://darcs.haskell.org/haskore/src/Haskore/Basic/TimeOrderedList.lhs
>
>
> > slice :: (Eq a, Num time) =>
> >    (body -> a) -> T time body -> [(a, T time body)]
> > slice f perf =
> >   let splitByHeadKey pf =
> >          fmap
> >             (\ev ->
> >                let i = f (eventBody ev)
> >                    (pf0, pf1) = partition ((i==) . f) 0 0 pf
> >                in  ((i,pf0), pf1))
> >             (listToMaybe pf)
> >   in  List.unfoldr splitByHeadKey perf
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Behavior of groupBy

Henning Thielemann

On Mon, 21 May 2007, Hans van Thiel wrote:

> Thanks for the help! Strangely, I just now received your messages from
> April 28, hence the late reply...

Our mail server does now send a bunch of mails I thought that were sent
long ago.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe