List Function

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

List Function

Nathan M. Holden
I don't know what you'd call it. Is there a function in any of the basic
functions that does this something like this:

Sending two lists, [1,2,3] and [2,3,4] it would return
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]. I managed to code
my way into returning a list of lists, which works. But it seemed like a
very basic list/matrix function, so I honestly believe that the Haskell
designers probably would've put it in.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090429/16efece4/attachment-0001.htm
Reply | Threaded
Open this post in threaded view
|

List Function

Edward Z. Yang
Excerpts from Nathan Holden's message of Wed Apr 29 22:25:43 -0400 2009:
> Sending two lists, [1,2,3] and [2,3,4] it would return
> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]. I managed to code
> my way into returning a list of lists, which works. But it seemed like a
> very basic list/matrix function, so I honestly believe that the Haskell
> designers probably would've put it in.

Did you mean [1,2,3] and [4,5,6]?

Cheers,
Edward
Reply | Threaded
Open this post in threaded view
|

List Function

jfredett
In reply to this post by Nathan M. Holden
So, two ways you could do it.

I assume your current function looks like:

    toPairs :: [a] -> [a] -> [[a]]
    toPairs [] _ = []
    toPairs (x:xs) ls = (zip (\y -> (x,y)) ls) : (toPairs xs ls)

This returns something like:

    toPairs [1,2] [3,4] ===> [[(1,3),(1,4)],[(2,3),(2,4)]]

We want a function that takes this list-of-lists to a list. We can
certainly see the type as:

    foo :: [[a]] -> [a]

`foo` would have to take all the elements of each list, and put it in a
new one. We know of a function which combines the elements of two lists,
(++)
so really, our foo function would do:

foo [] = []
foo (x:xs) = x ++ foo xs

concatenating all of the lists together in order. But this is just a
fold, we can call foo:

foo = foldr (++) -- or foldl would work too.

foldr is just the pattern above, abstracted away to a convenient function.

Of course, this function comes up all the time, so we have one in the
prelude, it's called. `concat`. and if you look up the source on hoogle,
I believe you'll find the above.

Nathan Holden wrote:

> I don't know what you'd call it. Is there a function in any of the
> basic functions that does this something like this:
>
> Sending two lists, [1,2,3] and [2,3,4] it would return
> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]. I managed to
> code my way into returning a list of lists, which works. But it seemed
> like a very basic list/matrix function, so I honestly believe that the
> Haskell designers probably would've put it in.
> ------------------------------------------------------------------------
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>  
-------------- next part --------------
A non-text attachment was scrubbed...
Name: jfredett.vcf
Type: text/x-vcard
Size: 296 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/beginners/attachments/20090429/e6863019/jfredett.vcf
Reply | Threaded
Open this post in threaded view
|

List Function

Edward Z. Yang
In reply to this post by Edward Z. Yang
Excerpts from Edward Z. Yang's message of Wed Apr 29 22:38:40 -0400 2009:
> Excerpts from Nathan Holden's message of Wed Apr 29 22:25:43 -0400 2009:
> > Sending two lists, [1,2,3] and [2,3,4] it would return
> > [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]. I managed to code
> > my way into returning a list of lists, which works. But it seemed like a
> > very basic list/matrix function, so I honestly believe that the Haskell
> > designers probably would've put it in.
>
> Did you mean [1,2,3] and [4,5,6]?

To elaborate, a list comprehension is what you want, if you want this function
to do what I think you want it to do.

Prelude> let f as bs = [(a,b) | a <- as, b <- bs]
Prelude> f [1,2,3] [4,5,6]
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Cheers,
Edward
Reply | Threaded
Open this post in threaded view
|

List Function

jfredett
In reply to this post by jfredett
Occurs to me I said two ways, and only gave one, the one I gave was the
tougher way. The easiest way is to use a list comprehension, viz:

    toPairs xs ys = [(x,y) | x <- xs, y <- ys]

This is nice and succint, you can think of it (assuming you're familiar
with it) as set-builder notation. The '[' and ']' brackets are the set
brackets '{' and '}'. '<-' is
roughly like the element symbol. You can even add constraints (called
guards), like so:

   foo xs ys = [x / y | x <- xs, y <- ys, y /= 0]



Joe Fredette wrote:

> So, two ways you could do it.
>
> I assume your current function looks like:
>
>    toPairs :: [a] -> [a] -> [[a]]
>    toPairs [] _ = []
>    toPairs (x:xs) ls = (zip (\y -> (x,y)) ls) : (toPairs xs ls)
>
> This returns something like:
>
>    toPairs [1,2] [3,4] ===> [[(1,3),(1,4)],[(2,3),(2,4)]]
>
> We want a function that takes this list-of-lists to a list. We can
> certainly see the type as:
>
>    foo :: [[a]] -> [a]
>
> `foo` would have to take all the elements of each list, and put it in
> a new one. We know of a function which combines the elements of two
> lists, (++)
> so really, our foo function would do:
>
> foo [] = []
> foo (x:xs) = x ++ foo xs
>
> concatenating all of the lists together in order. But this is just a
> fold, we can call foo:
>
> foo = foldr (++) -- or foldl would work too.
>
> foldr is just the pattern above, abstracted away to a convenient
> function.
>
> Of course, this function comes up all the time, so we have one in the
> prelude, it's called. `concat`. and if you look up the source on
> hoogle, I believe you'll find the above.
>
> Nathan Holden wrote:
>> I don't know what you'd call it. Is there a function in any of the
>> basic functions that does this something like this:
>>
>> Sending two lists, [1,2,3] and [2,3,4] it would return
>> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]. I managed to
>> code my way into returning a list of lists, which works. But it
>> seemed like a very basic list/matrix function, so I honestly believe
>> that the Haskell designers probably would've put it in.
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> Beginners mailing list
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/beginners
>>  
-------------- next part --------------
A non-text attachment was scrubbed...
Name: jfredett.vcf
Type: text/x-vcard
Size: 296 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/beginners/attachments/20090429/6e12a534/jfredett.vcf
Reply | Threaded
Open this post in threaded view
|

List Function

Brent Yorgey-2
In reply to this post by Nathan M. Holden
On Wed, Apr 29, 2009 at 10:25:43PM -0400, Nathan Holden wrote:
> I don't know what you'd call it. Is there a function in any of the basic
> functions that does this something like this:
>
> Sending two lists, [1,2,3] and [2,3,4] it would return
> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]. I managed to code
> my way into returning a list of lists, which works. But it seemed like a
> very basic list/matrix function, so I honestly believe that the Haskell
> designers probably would've put it in.

Others' answers are probably more helpful for learning, but I also
wanted to point out that there is a Prelude function that does
something close to this (assuming you meant [4,5,6]), namely,
'sequence'.

  Prelude> sequence [ [1,2,3], [4,5,6] ]
  [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
  Prelude> sequence [ [1,2], [3,4,5], [6,7] ]
  [[1,3,6],[1,3,7],[1,4,6],[1,4,7],[1,5,6],[1,5,7],[2,3,6],[2,3,7],[2,4,6],[2,4,7],[2,5,6],[2,5,7]]

However, explaining how/why sequence does this requires understanding
the list monad, which you may or may not want to tackle at this point.

If you import 'Control.Applicative' you can even do exactly what you
wanted, with pairs and all:

  Prelude Control.Applicative> liftA2 (,) [1,2,3] [4,5,6]
  [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Here, liftA2 is applying the function (,) to every possible pair of
values from the two lists.

-Brent
Reply | Threaded
Open this post in threaded view
|

List Function

Edward Z. Yang
Excerpts from Brent Yorgey's message of Wed Apr 29 23:41:03 -0400 2009:

> Others' answers are probably more helpful for learning, but I also
> wanted to point out that there is a Prelude function that does
> something close to this (assuming you meant [4,5,6]), namely,
> 'sequence'.
>
>   Prelude> sequence [ [1,2,3], [4,5,6] ]
>   [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
>   Prelude> sequence [ [1,2], [3,4,5], [6,7] ]
>  
> [[1,3,6],[1,3,7],[1,4,6],[1,4,7],[1,5,6],[1,5,7],[2,3,6],[2,3,7],[2,4,6],[2,4,7]
> ,[2,5,6],[2,5,7]]
>
> However, explaining how/why sequence does this requires understanding
> the list monad, which you may or may not want to tackle at this point.

Interesting! According to Hoogle, the sequence function evaluates each
monad and then collects the results. I know evaluating a list monad returns
a list, but what do they mean by "collect"?

> If you import 'Control.Applicative' you can even do exactly what you
> wanted, with pairs and all:
>
>   Prelude Control.Applicative> liftA2 (,) [1,2,3] [4,5,6]
>   [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
>
> Here, liftA2 is applying the function (,) to every possible pair of
> values from the two lists.

I'm not even going to try to understand that now.

Cheers,
Edward
Reply | Threaded
Open this post in threaded view
|

List Function

Yitzchak Gale
Brent Yorgey wrote:
>> ? Prelude Control.Applicative> liftA2 (,) [1,2,3] [4,5,6]
>> ? [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Edward Z. Yang wrote:
> I'm not even going to try to understand that now.

Brent used that because Applicative is even simpler
than Monad - at least theoretically. But it's less well
known at the moment.

If you want to stick to Monad, Brent's method works
there too:

  Prelude Control.Monad> liftM2 (,) [1,2,3] [4,5,6]
  [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

-Yitz
Reply | Threaded
Open this post in threaded view
|

Re: List Function

Heinrich Apfelmus
In reply to this post by Edward Z. Yang
Edward Z. Yang wrote:
>> However, explaining how/why sequence does this requires understanding
>> the list monad, which you may or may not want to tackle at this point.
>
> Interesting! According to Hoogle, the sequence function evaluates each
> monad and then collects the results. I know evaluating a list monad returns
> a list, but what do they mean by "collect"?

There is also  sequence_  which does not collect the results, but throws
them away.

    Prelude> sequence_ [ [1,2,3], [4,5,6] ]
    [(),(),(),(),(),(),(),(),()]


(Also, concerning terminology,  sequence  evaluates each monadic action.
You can't evaluate a monad, it's a type constructor, not a function or
value.)

>> If you import 'Control.Applicative' you can even do exactly what you
>> wanted, with pairs and all:
>>
>>   Prelude Control.Applicative> liftA2 (,) [1,2,3] [4,5,6]
>>   [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
>>
>> Here, liftA2 is applying the function (,) to every possible pair of
>> values from the two lists.
>
> I'm not even going to try to understand that now.

Also known as

    liftM2 (,) [1,2,3] [4,5,6]

Which is the same as

    do
       x <- [1,2,3]
       y <- [4,5,6]
       return (x,y)


Regards,
apfelmus

--
http://apfelmus.nfshost.com

Reply | Threaded
Open this post in threaded view
|

List Function

Brandon S Allbery KF8NH
In reply to this post by Edward Z. Yang
On Apr 29, 2009, at 23:57 , Edward Z. Yang wrote:

> Excerpts from Brent Yorgey's message of Wed Apr 29 23:41:03 -0400  
> 2009:
>>  Prelude> sequence [ [1,2,3], [4,5,6] ]
>>  [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
>>  Prelude> sequence [ [1,2], [3,4,5], [6,7] ]
>>
>> [[1,3,6],[1,3,7],[1,4,6],[1,4,7],[1,5,6],[1,5,7],[2,3,6],[2,3,7],
>> [2,4,6],[2,4,7]
>> ,[2,5,6],[2,5,7]]
>
> Interesting! According to Hoogle, the sequence function evaluates each
> monad and then collects the results. I know evaluating a list monad  
> returns
> a list, but what do they mean by "collect"?

In the list monad, "collect" means "concatenate".

--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [hidden email]
system administrator [openafs,heimdal,too many hats] [hidden email]
electrical and computer engineering, carnegie mellon university    KF8NH


-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 195 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/beginners/attachments/20090430/4c69132c/PGP.bin
Reply | Threaded
Open this post in threaded view
|

Re: List Function

Clint Moore-2
In reply to this post by Heinrich Apfelmus



> (Also, concerning terminology,  sequence  evaluates each monadic  
> action.
> You can't evaluate a monad, it's a type constructor, not a function or
> value.)

Ah ha!  I'm sure that it has been pointed out in some of the books  
that I have read, but for some reason reading that made all of the  
pieces suddenly fit together.  Thanks for that!