Monday, March 31, 2008
Finger Exercises
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" or sequence (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 M or equivalently Generate all unique ways to place M identical balls in N different buckets as 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 sequence in 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