Wow. Three months, no update. Hm.

I've been working on a bunch of little projects recently that individually don't amount to much, yet. I should have something to post about that soon.

In the mean time, here is a cute little problem (via Uri to the fun with Perl list):

What is an easy way to get all possible combinations of Y/N of length 5? (i.e., "YYYYY", "YYYYN", etc.)

Coming up with a solution to this exact problem seemed to cry out for a list comprehension:

[[a,b,c,d,e] | let l <- "YN",

a <- l, b <- l, c <- l, d <- l, e <- l]

but as soon as I wrote that, I saw how unsatisfactory it was. A better solution would produce all possible combinations of Y and N for a list of any integer *n* > 0:

yn i = (iterate f [""]) !! i

where f l = map ('Y':) l ++ map ('N':) l

This problem itself isn't very interesting, but it's good to have little diversions like this when you want to take a break while the coffee is steeping, waiting for the Guinness to settle, or whatnot. (Something that's more than a function from the Prelude, but less involved than something from Project Euler.)

Do you have any cute little "finger exercise" problems like these? I'd love to hear about them!

## 19 comments:

Hi,

"What is an easy way to get all possible combinations of Y/N of length 5?"

A shorter solution:

> sequence $ replicate 5 "YN"

Peter

ghci> :m +Control.Monad

ghci> replicateM 5 "YN"

I like writing little lambda-calculus interpreters. It's not too difficult but lets you stretch your mind, and there's always a hook for whatever new technique you are trying to understand.

Here's a somewhat cleaner solution"

yn 0 = [""]

yn n = return (:) `ap` "YN" `ap` yn (n-1)

r 0 = [[]]

r k = [a:x | a<-"yn", x<-r (k-1)]

main = print $ r 5

It's almost a prelude function: either

Control.Monad.replicateM 5 "YN"orsequence (replicate 5 "YN")Here's another implementation of yn:

yn i = sequence (replicate i "YN")

Which is about as good as I can see in "Haskell golf" (which is like Perl golf except you're going for the least inelegance). That's a bad solution though, because the tails vary faster than the heads, and thus there is no sharing (watch "length (yn 500)" eat up all your memory!). This is better:

sequence' [] = return []

sequence' (m:ms) = do {

xs <- sequence' ms;

x <- m;

return x;

}

yn i = sequence' (replicate i "YN")

It's really interesting to me that the "head-recursive" version has better performance after we've all learned to prefer tail recursion.

My favorite finger exercises recently have been dynamic programming exercises, such as:

http://projecteuler.net/index.php?section=problems&id=15

http://projecteuler.net/index.php?section=problems&id=67

Even easier:

yn = flip replicateM $ "YN"

The answer: sequence $ replicate 5 "YN"

Somewhat of a more clever way to do it (IMO):

Prelude Control.Monad Data.List> replicateM 5 "YN"

["YYYYY","YYYYN","YYYNY","YYYNN","YYNYY","YYNYN","YYNNY","YYNNN","YNYYY","YNYYN","YNYNY","YNYNN","YNNYY","YNNYN","YNNNY","YNNNN","NYYYY","NYYYN","NYYNY","NYYNN","NYNYY","NYNYN","NYNNY","NYNNN","NNYYY","NNYYN","NNYNY","NNYNN","NNNYY","NNNYN","NNNNY","NNNNN"]

Here is a fun relatively simple problem that actually appeared in a real program for me a few years ago:

Generate all unique lists of N positive integers whose sum is equal to Mor equivalentlyGenerate all unique ways to place M identical balls in N different bucketsas I like to think about it.For example with M = 3 and N = 3 it should give (in any order): [[0,0,3], [0,1,2], [0,2,1], [0,3,0], [1,0,2], [1,1,1], [1,2,0], [2,0,1], [2,1,0], [3,0,0]]

Writing a recursive function that solved this was pretty easy, but I suspect it can be written as a oneliner by someone with better Haskell-Fu than me. :)

Happy hacking.

replicateM 5 "YN"

a simpler way to do this in Haskell is:

mapM (const "FT") [1..5]

-John

shorter yet is

replicateM 5 "FT"

-John

Any time you need combinations, think

sequencein the List monad:yn i = sequence (replicate i "YN")

Cheers,

Tom

You mean

sequence $ replicate 5 "YN"

On that particular problem: any "all possible x" problem leads me to the list monad; in this case, a 'dynamic' version of your list comprehension:

sequence (replicate 5 "YN")

I have a favorite solution to this problem:

yn i = replicateM "YN" i

Understanding this solution is a worthy exercise on its own.

What's wrong with 'replicateM 5 "YN"' ? =)

@Tirpen, it's not the most efficient way to do it, but here's a oneliner anyway:

ways n m = filter ((== m).sum) $ replicateM n [0..m]

Post a Comment