tag:blogger.com,1999:blog-6655746112052720933.post4725155310638692688..comments2022-03-30T18:43:33.525-05:00Comments on Notes on Haskell: Finger ExercisesAdam Turoffhttp://www.blogger.com/profile/11941071792943377879noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-6655746112052720933.post-5165587748140716132008-04-01T22:39:00.000-05:002008-04-01T22:39:00.000-05:00@Tirpen, it's not the most efficient way to do it,...@Tirpen, it's not the most efficient way to do it, but here's a oneliner anyway:<BR/><BR/>ways n m = filter ((== m).sum) $ replicateM n [0..m]bd_https://www.blogger.com/profile/01560746058527855728noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-7432897198203161812008-04-01T14:30:00.000-05:002008-04-01T14:30:00.000-05:00What's wrong with 'replicateM 5 "YN"' ? =)What's wrong with 'replicateM 5 "YN"' ? =)Brenthttps://www.blogger.com/profile/14440861005012132386noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-33625406379381334722008-04-01T13:07:00.000-05:002008-04-01T13:07:00.000-05:00I have a favorite solution to this problem: yn ...I have a favorite solution to this problem:<BR/><BR/> yn i = replicateM "YN" i<BR/><BR/>Understanding this solution is a worthy exercise on its own.Spencer Janssenhttps://www.blogger.com/profile/03654919351290552084noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-78494156399621780852008-04-01T11:35:00.000-05:002008-04-01T11:35:00.000-05:00On that particular problem: any "all possible x" p...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:<BR/><BR/>sequence (replicate 5 "YN")Kevin Reidhttps://www.blogger.com/profile/13879815484727290360noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-67222038997067800822008-04-01T10:43:00.000-05:002008-04-01T10:43:00.000-05:00You meansequence $ replicate 5 "YN"You mean<BR/><BR/>sequence $ replicate 5 "YN"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-5451800165569840192008-04-01T09:00:00.000-05:002008-04-01T09:00:00.000-05:00Any time you need combinations, think sequence in ...Any time you need combinations, think <I>sequence</I> in the List monad:<BR/><BR/>yn i = sequence (replicate i "YN")<BR/><BR/>Cheers,<BR/>TomAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-91560870059587983552008-04-01T08:05:00.000-05:002008-04-01T08:05:00.000-05:00shorter yet is replicateM 5 "FT"-Johnshorter yet is<BR/><BR/> replicateM 5 "FT"<BR/><BR/>-Johntromphttps://www.blogger.com/profile/16161842727664839561noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-21330336977525308872008-04-01T08:03:00.000-05:002008-04-01T08:03:00.000-05:00a simpler way to do this in Haskell is: mapM (con...a simpler way to do this in Haskell is:<BR/><BR/> mapM (const "FT") [1..5]<BR/><BR/>-Johntromphttps://www.blogger.com/profile/16161842727664839561noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-41317418669461374262008-04-01T05:42:00.000-05:002008-04-01T05:42:00.000-05:00replicateM 5 "YN"replicateM 5 "YN"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-61640719006270316542008-04-01T05:27:00.000-05:002008-04-01T05:27:00.000-05:00Here is a fun relatively simple problem that actua...Here is a fun relatively simple problem that actually appeared in a real program for me a few years ago:<BR/> <B>Generate all unique lists of N positive integers whose sum is equal to M</B> or equivalently <B> Generate all unique ways to place M identical balls in N different buckets</B> as I like to think about it.<BR/> 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]]<BR/> 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. :)<BR/> Happy hacking.Anonymoushttps://www.blogger.com/profile/10900250988738447307noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-56002436627336870392008-04-01T03:14:00.000-05:002008-04-01T03:14:00.000-05:00Somewhat of a more clever way to do it (IMO):Prelu...Somewhat of a more clever way to do it (IMO):<BR/><BR/>Prelude Control.Monad Data.List> replicateM 5 "YN"<BR/>["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"]bd_https://www.blogger.com/profile/01560746058527855728noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-17494639325844686562008-04-01T02:59:00.000-05:002008-04-01T02:59:00.000-05:00The answer: sequence $ replicate 5 "YN"The answer: sequence $ replicate 5 "YN"Neil Mitchellhttps://www.blogger.com/profile/13084722756124486154noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-76523887485661346422008-03-31T23:38:00.000-05:002008-03-31T23:38:00.000-05:00Even easier:yn = flip replicateM $ "YN"Even easier:<BR/><BR/>yn = flip replicateM $ "YN"Unknownhttps://www.blogger.com/profile/16303505992331612487noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-11481916149203659642008-03-31T23:31:00.000-05:002008-03-31T23:31:00.000-05:00Here's another implementation of yn:yn i = sequenc...Here's another implementation of yn:<BR/><BR/>yn i = sequence (replicate i "YN")<BR/><BR/>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:<BR/><BR/>sequence' [] = return []<BR/>sequence' (m:ms) = do {<BR/> xs <- sequence' ms;<BR/> x <- m;<BR/> return x;<BR/>}<BR/>yn i = sequence' (replicate i "YN")<BR/><BR/>It's really interesting to me that the "head-recursive" version has better performance after we've all learned to prefer tail recursion.<BR/><BR/>My favorite finger exercises recently have been dynamic programming exercises, such as:<BR/><BR/>http://projecteuler.net/index.php?section=problems&id=15<BR/>http://projecteuler.net/index.php?section=problems&id=67Luke Palmerhttps://www.blogger.com/profile/09807388788677769669noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-15446013160087547482008-03-31T22:45:00.000-05:002008-03-31T22:45:00.000-05:00It's almost a prelude function: either Control.Mon...It's almost a prelude function: either <I>Control.Monad.replicateM 5 "YN"</I> or <I>sequence (replicate 5 "YN")</I>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-16039658319983320872008-03-31T22:43:00.000-05:002008-03-31T22:43:00.000-05:00r 0 = [[]]r k = [a:x | amain = print $ r 5r 0 = [[]]<BR/>r k = [a:x | a<-"yn", x<-r (k-1)]<BR/><BR/>main = print $ r 5Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-57981559326006752762008-03-31T22:31:00.000-05:002008-03-31T22:31:00.000-05:00Here's a somewhat cleaner solution"yn 0 = [""]yn n...Here's a somewhat cleaner solution"<BR/><BR/>yn 0 = [""]<BR/>yn n = return (:) `ap` "YN" `ap` yn (n-1)Christophe Poucethttps://www.blogger.com/profile/02320035941417593372noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-37622815559256943552008-03-31T22:29:00.000-05:002008-03-31T22:29:00.000-05:00ghci> :m +Control.Monadghci> replicateM 5 "Y...ghci> :m +Control.Monad<BR/>ghci> replicateM 5 "YN"<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-74219861486718079352008-03-31T22:17:00.000-05:002008-03-31T22:17:00.000-05:00Hi,"What is an easy way to get all possible combin...Hi,<BR/><BR/>"What is an easy way to get all possible combinations of Y/N of length 5?"<BR/><BR/>A shorter solution:<BR/><BR/>> sequence $ replicate 5 "YN"<BR/><BR/>PeterAnonymousnoreply@blogger.com