Help with generalizing function
I've successfully create a function to return lists of N-ple that satisfy the following function: x1 + x2 + x3 + ... + xN = C But unfortunately, it's not generic. The N is supposed to be an input, too. I don't know how to make a dynamic N-ple (is it possible anyway?). Currently, here's the implementation: [code] findAllAns c = [ (x1,x2,x3,x4,x5) | x1 <- [0..c], x2 <- [0..c], x3 <- [0..c], x4 <- [0..c], x5 <- [0..c], x1 + x2 + x3 + x4 + x5 == c ] [/code] I tried using lists of lists, like this: [code] findAllAns c n = [ [x] | x <- [0..c], length [x] == n ] [/code] but [x] doesn't mean "a list of x", instead it's "a list that contains an x, where x in [0..c]". Can anyone help me? -- View this message in context: http://www.nabble.com/Help-with-generalizing-function-tp18063291p18063291.ht... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
Hint: use recursion.
Hint 2: You can use <- in a list comprehension or list "do"-block to
select a single list from a list of lists.
-- ryan
On Sun, Jun 22, 2008 at 11:30 PM, leledumbo
I've successfully create a function to return lists of N-ple that satisfy the following function: x1 + x2 + x3 + ... + xN = C But unfortunately, it's not generic. The N is supposed to be an input, too. I don't know how to make a dynamic N-ple (is it possible anyway?). Currently, here's the implementation: [code] findAllAns c = [ (x1,x2,x3,x4,x5) | x1 <- [0..c], x2 <- [0..c], x3 <- [0..c], x4 <- [0..c], x5 <- [0..c], x1 + x2 + x3 + x4 + x5 == c ] [/code] I tried using lists of lists, like this: [code] findAllAns c n = [ [x] | x <- [0..c], length [x] == n ] [/code] but [x] doesn't mean "a list of x", instead it's "a list that contains an x, where x in [0..c]". Can anyone help me? -- View this message in context: http://www.nabble.com/Help-with-generalizing-function-tp18063291p18063291.ht... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
tuples may contain any combination of types, use lists instead I think so, too.
You can use <- in a list comprehension or list "do"-block to select a single list from a list of lists. Is it related with my question? I mean, instead of extracting, I need to construct lists. -- View this message in context: http://www.nabble.com/Help-with-generalizing-function-tp18063291p18064396.ht... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
On Mon, Jun 23, 2008 at 6:30 AM, leledumbo
I've successfully create a function to return lists of N-ple that satisfy the following function: x1 + x2 + x3 + ... + xN = C But unfortunately, it's not generic. The N is supposed to be an input, too. I don't know how to make a dynamic N-ple (is it possible anyway?). Currently, here's the implementation: [code] findAllAns c = [ (x1,x2,x3,x4,x5) | x1 <- [0..c], x2 <- [0..c], x3 <- [0..c], x4 <- [0..c], x5 <- [0..c], x1 + x2 + x3 + x4 + x5 == c ] [/code]
You will not be able to do this with a straight list comprehension without using recursion. It may help you to know that: [ e | x <- as, y <- bs ] -- for any expression e Is equivalent to concat [ [ e | y <- bs ] | x <- as ] That is a way commas in list comprehensions can be factored out. Luke
I give up %-|, I'll go back to Pascal instead. Thanks for your answers. -- View this message in context: http://www.nabble.com/Help-with-generalizing-function-tp18063291p18065206.ht... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
2008/6/23 leledumbo
I give up %-|, I'll go back to Pascal instead. Thanks for your answers.
Don't give up so fast !! (Note that you can't do what you asked for in Pascal either, in fact Pascal don't support n-uplet) A recursive way to do it is : findAllAns 0 0 = [[]] findAllAns 0 s = [] findAllAns n s = [ x:xs | x <- [0..s], xs <- findAllAns (n - 1) (s - x) ] For all those little questions that bug you, you'll get your answers faster by asking on the #haskell channel on irc.freenode.org . -- Jedaï
Hello Chaddai, Monday, June 23, 2008, 1:42:25 PM, you wrote:
I give up %-|, I'll go back to Pascal instead. Thanks for your answers.
findAllAns 0 0 = [[]] findAllAns 0 s = [] findAllAns n s = [ x:xs | x <- [0..s], xs <- findAllAns (n - 1) (s - x) ]
seems that leledumbo found a new way to force us give the answers to those homeworks LOL -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
>> Don't give up so fast !! (Note that you can't do what you asked for in >> Pascal either, in fact Pascal don't support n-uplet) I'm not going to use n-uplet, dynamic array of array of Byte is enough. Though not very optimizing, I can use 2 step process: 1. Generate all lists (array of Byte) of length N which each element ranges from 0 to C. 2. Filter which has sum=C. >> seems that leledumbo found a new way to force us give the answers to >> those homeworks LOL Don't worry, I'm not gonna use it because it has to be done in procedural way (I haven't taken Functional Programming class yet). The reason why I ask is I'm HOPING that if I can understand how it works, implementing the procedural form would be easy. I've read somewhere that functional language can be implemented in procedural one. In fact, GHC outputs C code. Thanks for the answer. I'll use it to learn, it's quite difficult to switch from procedural to functional. I mean, in procedural it's easy to find the fastest solution using brute force. This can't be done in functional. -- View this message in context: http://www.nabble.com/Help-with-generalizing-function-tp18063291p18066860.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
On Mon, 2008-06-23 at 04:03 -0700, leledumbo wrote:
Don't give up so fast !! (Note that you can't do what you asked for in Pascal either, in fact Pascal don't support n-uplet) I'm not going to use n-uplet, dynamic array of array of Byte is enough. Though not very optimizing, I can use 2 step process:
1. Generate all lists (array of Byte) of length N which each element ranges from 0 to C.
Come now, you really think this is harder in Haskell than in Pascal? Understanding Haskell takes a little work, granted, but then I always thought the same was true of Pascal...
2. Filter which has sum=C.
Come now. Try your browser's search engine on the standard prelude, word by word. You can't really expect this to be just given to you, but you must realise that sometimes it is...
seems that leledumbo found a new way to force us give the answers to those homeworks LOL Don't worry, I'm not gonna use it because it has to be done in procedural way (I haven't taken Functional Programming class yet). The reason why I ask is I'm HOPING that if I can understand how it works, implementing the procedural form would be easy. I've read somewhere that functional language can be implemented in procedural one. In fact, GHC outputs C code.
Thanks for the answer. I'll use it to learn, it's quite difficult to switch from procedural to functional. I mean, in procedural it's easy to find the fastest solution using brute force.
Huh? The brute force solution is usually the /slowest/ solution, even in imperative languages. Consider bubble sort (bogo sort if you want to push it) vs. quick sort.
This can't be done in functional.
If you mean `find a brute-force solution quickly', getting to the brute force solution is indeed usually /faster/ in a functional language (it's usually shorter, too), because of the higher level of abstraction. (The same is true for other modern languages, such as Perl, Ruby, to a certain extent Python, and soon enough (hopefully) PHP, but then it's questionable in what way the languages (as opposed to their programming cultures) fail to be functional in the first place). jcc
>> Don't give up so fast !! (Note that you can't do what you asked for in >> Pascal either, in fact Pascal don't support n-uplet) I'm not going to use n-uplet, dynamic array of array of Byte is enough. Though not very optimizing, I can use 2 step process: 1. Generate all lists (array of Byte) of length N which each element ranges from 0 to C. 2. Filter which has sum=C. >> seems that leledumbo found a new way to force us give the answers to >> those homeworks LOL Don't worry, I'm not gonna use it because it has to be done in procedural way (I haven't taken Functional Programming class yet). The reason why I ask is I'm HOPING that if I can understand how it works, implementing the procedural form would be easy. I've read somewhere that functional language can be implemented in procedural one. In fact, GHC outputs C code. Thanks for the answer. I'll use it to learn, it's quite difficult to switch from procedural to functional. I mean, in procedural it's easy to find the fastest solution using brute force. This can't be done in functional. -- View this message in context: http://www.nabble.com/Help-with-generalizing-function-tp18063291p18066861.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
Hi, I'm back. I have some troubles understanding your code: Chaddaï Fouché-2 wrote:
findAllAns 0 0 = [[]] findAllAns 0 s = [] findAllAns n s = [ x:xs | x <- [0..s], xs <- findAllAns (n - 1) (s - x) ]
Let's try a test case (CMIIW) for findAllAns 2 1: findAllAns 2 1 = [ 0:(findAllAns 1 1) ] = [ 0:0:(findAllAns 0 1) ] = [ 0:0:[] ] // Not a solution = [ 0:(findAllAns 1 1) ] = [ 0:1:(findAllAns 0 0) ] = [ 0:1:[[]] ] // A solution = [ 1:(findAllAns 1 0) ] = [ 1:0:(findAllAns 0 0) ] = [ 1:0:[[]] ] // A solution ( 1:1:? is never reached. ) I don't understand why if the last element is [[]] then it's included in the result and not if it's []. -- View this message in context: http://www.nabble.com/Help-with-generalizing-function-tp18063291p18106999.ht... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
2008/6/25 leledumbo
Hi, I'm back. I have some troubles understanding your code:
( 1:1:? is never reached. )
Why would 1:1 be reached when we search for lists with a sum of 1 ?? Your derivation is incorrect, when you're reading a list comprehension you must see it as imbricated loops, let's see a correct derivation : findAllAns 2 1 ==> [ x:xs | x <- [0..1], xs <- findAllAns 1 (1 - x) ] ==> concat [ [ 0 : xs | xs <- findAllAns 1 1 ], [ 1 : xs | xs <- findAllAns 1 0 ] ] findAllAns 1 1 ==> [ concat [ [ [ 0 : xs | xs <- findAllAns 0 1 ], [ 1 : xs | xs <- findAllAns 0 0 ] ] ==> concat [ [], [[1]] ] ==> [ [ 1 ] ] In reality, all list comprehensions are translated to ordinary functions under the hood, the translation is the following : [ x:xs | x <- [0..s], xs <- findAllAns (n - 1) (s - x) ] == concatMap (x -> concatMap (\xs -> x : xs) (findAllAns (n - 1) (s - x)) [0..s] which is then easier to derive.
I don't understand why if the last element is [[]] then it's included in the result and not if it's [].
I think with the concatMap above you'll understand better what's going on : "concatMap (\xs -> 0 : xs) (findAllAns 0 1)" returns the empty list because "findAllAns 0 1" is an empty list while "concatMap (\xs -> 1 : xs) (findAllAns 0 0)" returns [[1]] because "findAllAns 0 0" is a list that contains the empty list. But you don't have to think so hard to find the good response, just think of the edge cases logically : faire une somme de 0 avec 0 éléments c'est possible (parce que 0 est l'élément neutre de l'addition), tandis que faire une somme différente de 0 avec 0 éléments est impossible. (The sum of 0 elements is always 0, and the product of 0 elements is always 1) -- Jedaï
On 23 Jun 2008, at 6:30 pm, leledumbo wrote:
I've successfully create a function to return lists of N-ple that satisfy the following function: x1 + x2 + x3 + ... + xN = C But unfortunately, it's not generic.
Why do you want it to be a tuple? All the elements are the same type, so it might as well be a list. part 0 c | c == 0 = [[]] part (n+1) c | c >= 0 = [(x:xs) | x <- [0..c], xs <- part n (c-x)] (WARNING: UNTESTED CODE!) Knuth TAOCP Volume 4 has some stuff on enumerating partitions.
participants (7)
-
Bulat Ziganshin -
Chaddaï Fouché -
Jonathan Cast -
leledumbo -
Luke Palmer -
Richard A. O'Keefe -
Ryan Ingram