List comprehensions with multiple generators

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

List comprehensions with multiple generators

Ken Overton-2
Hello all,

I recently came across this function which made me realize I don't understand list comprehensions well. I hope someone can help me understand them better by understanding this example better. The function takes a list of Eq and returns the list of unique elements from it:

    unique :: Eq a => [a] -> [a]
    unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]

It's using a list comprehension with multiple 'generators' (hope I have the term correctly). My understanding of multiple generators in a list comprehension is that they refine the results of the previous generator.

So the first generator should produce [(Eq,Int)] as input to the second generator? And the second generator should produce [Bool]?

My understanding must be wrong though; how do we end up with just the items where the second generator produced True?

Thanks,


--
Ken Overton
(917) 863-3937


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: List comprehensions with multiple generators

Ut Primum
Hi,
I'll try to explain the meaning of different parts of the comprehension::

unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)] 
this part means: consider the couples (x,y) that are output of zip xs [0..]
for example if xs = [10,20,10,30,30], you are taking [(10,0),(20,1),(10,2),(30,3),(30,4)]

unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]  
this part means: among the things you considered before (i.e. all the couples obtained before), consider only those that satisfy the property that the first element of (x,y) is not an alement of a certain list (take y xs, i.e. the first y elements of xs).
So in the example above: 
      is 10 an element of (take 0 xs)=[ ] ? No ----> we consider (10,0)
      is 20 an element of (take 1 xs)=[10]? No ----> we consider (20,1)
      is 10 an element of (take 2 xs)=[10,20]? Yes ----> we DON'T consider (10,2)
      is 30 an element of (take 3 xs)=[10,20,10]? No ----> we consider (30,3)
      is 30 an element of (take 4 xs)=[10,20,10,30]? Yes ----> we DON'T consider (30,4)
So we are considering only [(10,0),(20,1),(30,3)]
So as you said this is a refinement of the elements generated by the first generator. A refinement means that some of the elements generated before are (possibly) discarded, so you don't obtain a [Bool], but something of the same type of what was generated before, i.e. another [(Eq,Int)] possibly shorter than the previous one.

Finally
unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]  
this part says that, of each couple produced and refined before, you take the first element (that was called x).
So in the example you get [10,20,30] 

Hope this is clear,
Ut

Il giorno dom 26 apr 2020 alle ore 14:51 Ken Overton <[hidden email]> ha scritto:
Hello all,

I recently came across this function which made me realize I don't understand list comprehensions well. I hope someone can help me understand them better by understanding this example better. The function takes a list of Eq and returns the list of unique elements from it:

    unique :: Eq a => [a] -> [a]
    unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]

It's using a list comprehension with multiple 'generators' (hope I have the term correctly). My understanding of multiple generators in a list comprehension is that they refine the results of the previous generator.

So the first generator should produce [(Eq,Int)] as input to the second generator? And the second generator should produce [Bool]?

My understanding must be wrong though; how do we end up with just the items where the second generator produced True?

Thanks,


--
Ken Overton
(917) 863-3937

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: List comprehensions with multiple generators

Francesco Ariis
In reply to this post by Ken Overton-2
Hello Ken,

On Sun, Apr 26, 2020 at 08:50:20AM -0400, Ken Overton wrote:

> I recently came across this function which made me realize I don't
> understand list comprehensions well. I hope someone can help me understand
> them better by understanding this example better. The function takes a list
> of Eq and returns the list of unique elements from it:
>
>     unique :: Eq a => [a] -> [a]
>     unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]
>
>
> [...]
>
> So the first generator should produce [(Eq,Int)] as input to the second
> generator? And the second generator should produce [Bool]?

1. (x,y) <- zip xs [0..] -- generates a list of pairs.
2. x `notElem` (take y xs) -- acts like a guard to 1., so only the `x`s
   which are not in the first `y` elements of `xs` (in other words, the
   previous elements of `xs`) will be returned.

The examples on the wiki [1] show more way of using list
comprehensions.

[1] https://wiki.haskell.org/List_comprehension#Examples
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: List comprehensions with multiple generators

Ken Overton-2
I see now, thanks to both of you; I think I was thrown off by the term 'generators' -- the 'refinement' provided by the second generator is more like filter rather than map.

I guess if I actually wanted the case all the pairs were evaluated and resulted in [Bool] where the first occurrence of an item were True, rather than multiple generators I would have two nested list comprehensions? 

Thanks everyone,

On Sun, Apr 26, 2020 at 9:39 AM Francesco Ariis <[hidden email]> wrote:
Hello Ken,

On Sun, Apr 26, 2020 at 08:50:20AM -0400, Ken Overton wrote:
> I recently came across this function which made me realize I don't
> understand list comprehensions well. I hope someone can help me understand
> them better by understanding this example better. The function takes a list
> of Eq and returns the list of unique elements from it:
>
>     unique :: Eq a => [a] -> [a]
>     unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]
>
>
> [...]
>
> So the first generator should produce [(Eq,Int)] as input to the second
> generator? And the second generator should produce [Bool]?

1. (x,y) <- zip xs [0..] -- generates a list of pairs.
2. x `notElem` (take y xs) -- acts like a guard to 1., so only the `x`s
   which are not in the first `y` elements of `xs` (in other words, the
   previous elements of `xs`) will be returned.

The examples on the wiki [1] show more way of using list
comprehensions.

[1] https://wiki.haskell.org/List_comprehension#Examples
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


--
Ken Overton
(917) 863-3937


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: List comprehensions with multiple generators

Francesco Ariis
On Sun, Apr 26, 2020 at 10:26:48AM -0400, Ken Overton wrote:
> I guess if I actually wanted the case all the pairs were evaluated and
> resulted in [Bool] where the first occurrence of an item were True, rather
> than multiple generators I would have two nested list comprehensions?

I am not sure I understand what you are trying to achieve, but there
is always the possibility of bringing the `y` and the "filter" before
the guard:

    uniqueInternal :: Eq a => [a] -> [(a, Int, Bool)]
    uniqueInternal xs = [(x,y, x `notElem` take y xs) | (x,y) <- zip xs [0..]]

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners