"listProduct" -- is this a standard function?
I've constructed a "listProduct" function that I think I've seen somewhere else... is it a standard function? If so, where is it defined? My code is: [[ -- |Given a list of lists, construct a new list of lists where -- each member of the new list is the same length as the original -- list, and each member corresponds to a different choice of -- one element from each of the original members in the -- corresponding position. Thus: -- -- listProduct [[a1,a2],[b1],[c1,c2]] = -- [ [a1,b1,c1], [a1,b1,c2], [a2,b1,c1], [a2,b1,c2] ] -- -- Note: The length of the resulting list is the product of -- lengths of the components of the original list. Thus, if -- any member of the original list is empty then so is the -- resulting list: -- -- listProduct [[a1,a2],[],[c1,c2]] = [] -- listProduct :: [[a]] -> [[a]] listProduct [] = [[]] listProduct (as:ass) = concat [ map (a:) (listProduct ass) | a <- as ] test1 = listProduct [["a1","a2"],["b1"],["c1","c2"]] test2 = listProduct [["a1","a2"],[],["c1","c2"]] ]] And a supplementary point. Following a comment made to me previously, I can replace this list comprehension (not having any guard expressions) with another map function, thus: [[ lp [] = [[]] lp (as:ass) = concatMap (\a -> (map (a:) (lp ass))) as ]] I think I should also be able to eliminate the lambda-abstraction, but I can't see how. I prefer the list comprehension, as I find that easier to read than the \-expression. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
On Wed, 15 Oct 2003 17:07:00 +0100
Graham Klyne
[[ lp [] = [[]] lp (as:ass) = concatMap (\a -> (map (a:) (lp ass))) as ]]
I think I should also be able to eliminate the lambda-abstraction, but I can't see how. I prefer the list comprehension, as I find that easier to read than the \-expression.
lp (as:ass) = concatMap (flip map (lp ass) . (:)) as but better, lp = sequence
On Wednesday 15 October 2003 11:07 am, Graham Klyne wrote:
I've constructed a "listProduct" function that I think I've seen somewhere else... is it a standard function? If so, where is it defined?
Yes. It's called "sequence". It's defined in the prelude. It works with arbitrary monads, not just lists. I think that's pretty cool. 8-) Matt Harden
At 22:04 15/10/03 -0500, Matt Harden wrote:
On Wednesday 15 October 2003 11:07 am, Graham Klyne wrote:
I've constructed a "listProduct" function that I think I've seen somewhere else... is it a standard function? If so, where is it defined?
Yes. It's called "sequence". It's defined in the prelude. It works with arbitrary monads, not just lists.
That's the one, thanks (both of you). I *thought* I'd seen this function before. I observe this seems to be a recurring problem for me... there are so many very generic and useful data handling functions in Haskell, it's difficult for a jobbing programmer (as opposed to a language expert) to be on top of them all. And the very generic nature of these function means that it's not so easy to index them (e.g. in the way that the Java Developers Almanac series does for Java). Am I overlooking any important developer resources? #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
Somehow I managed to overlook about five replies. Sorry. I'll try to say something more useful than "sequence" here, my advice for finding functions.
I observe this seems to be a recurring problem for me... there are so many very generic and useful data handling functions in Haskell, it's difficult for a jobbing programmer (as opposed to a language expert) to be on top of them all. And the very generic nature of these function means that it's not so easy to index them (e.g. in the way that the Java Developers Almanac series does for Java).
Am I overlooking any important developer resources?
#g
All I know of is the GHC haddock docs and the libraries page on haskell.org. Generic functions usually live in Control for generic combinators, or Data.X for cata/ana/confusomorphisms over X. I don't think it's that hard to find generic functions if you remember to look for your operations as generic functions. Try to think of the most general type the operation you want can sensibly have, and you'll have a better chance of finding it. If you look for mapInt::(Int -> Int) -> [Int] -> [Int] you might check Data.Int and find nothing. If you generalize to (a -> b) -> [a] -> [b] you can notice the only concrete types are list and arrow constructors and think this is probably in Data.List somewhere, or maybe in Control. The suggestion of a "types that specialize to/unify with this type" search would be really useful. Brandon
At 16:38 17/10/03 -0700, Brandon Michael Moore wrote:
The suggestion of a "types that specialize to/unify with this type" search would be really useful.
My main interest in Haskell is as a "scripting language" for semantic web applications (cf [1] et seq). Your comment suggests a possible application that might be built from the tools I'm currently developing [4]. I would guess it would be feasible to modify Haddock to generate RDF [2] descriptions of library functions as an alternative to HTML (or, maybe better still, generate a form of XHTML with additional embedded markup that can be used to extract RDF from HTML using a simple XSLT stylesheet, cf. [3]). It would be an interesting test of my inference toolkit to see if it can handle the unification required to match function signatures for this; I think it would be moderately straightforward to do in bare Haskell (not having to worry too much about language corner cases for such an application). #g -- [1] http://www.haskell.org/pipermail/haskell/2003-February/011222.html -- cites article about what makes a popular language: http://www.paulgraham.com/popular.html [2] http://www.w3.org/TR/REC-rdf-syntax/ and http://www.w3.org/RDF/ [3] http://www.w3.org/2001/sw/Europe/200207/rsscal/xslt-rss-events.html -- This is an example of using one of several techniques described in: http://infomesh.net/2002/rdfinhtml/ [4] http://www.haskell.org/pipermail/haskell/2003-June/012013.html -- Announcing first phase of my Swish software, with links ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
participants (4)
-
Brandon Michael Moore -
Derek Elkins -
Graham Klyne -
Matt Harden