Haskell Nested List Generators

Question

This is a problem I've been working through on List comprehension. I know that it should be solved with recursion, but I am not sure exactly how the Haskell syntax works for the recursive case.

Here's the problem:

Given a list of strings, output all possible combinations of those strings and 3 variables [C,U,I]. For example,

list ["vC", "vU", "vI"] ==
                 [[("vC",C),("vU",C),("vI",C)],[("vC",I),("vU",C),("vI",C)],[("vC",U),("vU",C),("vI",C)]
                 ,[("vC",C),("vU",I),("vI",C)],[("vC",I),("vU",I),("vI",C)],[("vC",U),("vU",I),("vI",C)]
                 ,[("vC",C),("vU",U),("vI",C)],[("vC",I),("vU",U),("vI",C)],[("vC",U),("vU",U),("vI",C)]
                 ,[("vC",C),("vU",C),("vI",I)],[("vC",I),("vU",C),("vI",I)],[("vC",U),("vU",C),("vI",I)]
                 ,[("vC",C),("vU",I),("vI",I)],[("vC",I),("vU",I),("vI",I)],[("vC",U),("vU",I),("vI",I)]
                 ,[("vC",C),("vU",U),("vI",I)],[("vC",I),("vU",U),("vI",I)],[("vC",U),("vU",U),("vI",I)]
                 ,[("vC",C),("vU",C),("vI",U)],[("vC",I),("vU",C),("vI",U)],[("vC",U),("vU",C),("vI",U)]
                 ,[("vC",C),("vU",I),("vI",U)],[("vC",I),("vU",I),("vI",U)],[("vC",U),("vU",I),("vI",U)]
                 ,[("vC",C),("vU",U),("vI",U)],[("vC",I),("vU",U),("vI",U)],[("vC",U),("vU",U),("vI",U)]]

Edit: So this is what I have tried so far.

list :: [String] -> [Dict]
list [] = [[]]
list xs = [[(x,y)] | y<-[C,U,I], x <- xs]

However, when I run a test case with three variables, it only outputs:

[[("vC",C)],[("vU",C)],[("vI",C)],[("vC",U)],[("vU",U)],[("vI",U)],[("vC",I)],[("vU",I)],[("vI",I)]]

What's the question? What did you attempt? Why didn't it work? — Vincent Savard
– Vincent Savard, Commented May 19, 2016 at 16:07
could you show us what you have tried, this seems like homework/exercise! Please show as much effort as you would expect someone answering the question putting into writing the answer. A good start would be reading the info-page => section Free Haskell Programming Books — epsilonhalbe
– epsilonhalbe, Commented May 19, 2016 at 16:10
Edited the original post to add what I have tried so far and why it has failed. Thanks for the resource. — lancer
– lancer, Commented May 19, 2016 at 16:32
try to tweak this a bit: let list [] = [[]]; list (x:xs) = [(x,c) : ys | c <-???, ys <- ??? ] ... hint: recursion is a good idea / the order might be wrong ;) — Random Dev
– Random Dev, Commented May 19, 2016 at 16:42

Random Dev · Accepted Answer · 2016-05-19 18:47:04Z

1

ok, let's try to get you there step by step

Maybe you've seen the comment already but here it is with the most important step but in:

list []     = [[]]
list (x:xs) = [(x,c) : ys | c <- ???, ys <- list xs ]

notice the two cases corresponding to the two list-constructors - that's typical and you missed the second one.

Now you only have to:

fill in the ??? it should be easy
figure out how to fix the order (IMO it will help you understand) so that it will be exactly what your example did

I guess you got it - just in case the answer is:

list []     = [[]]
list (x:xs) = [(x,c) : ys | ys <- list xs, c <- [C,I,U] ]

edited May 19, 2016 at 18:47

answered May 19, 2016 at 18:11

Random Dev

52.4k9 gold badges95 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

lancer Over a year ago

I did work out the solution and have marked your answer as such. Thanks Carsten.

Collectives™ on Stack Overflow

Haskell Nested List Generators

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related