<div dir="ltr"><div dir="ltr"><div dir="ltr">Here are two mechanical strategies for implementing DP in haskell:<div><br></div><div><div><font face="courier new, monospace">module Main where</font></div><div><font face="courier new, monospace">import Data.Map.Strict as Map</font></div><div><font face="courier new, monospace">import Data.Vector as Vec</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">-- The recursive step</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">rec :: (Int -> [[Int]]) -> Int -> [[Int]]</font></div><div><font face="courier new, monospace">rec rec n = do</font></div><div><font face="courier new, monospace"> this <- [1..n]</font></div><div><font face="courier new, monospace"> other <- rec (n - this)</font></div><div><font face="courier new, monospace"> return $ (this : other)</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">-- Non-dynamic</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">sumsTo1 :: Int -> [[Int]]</font></div><div><font face="courier new, monospace">sumsTo1 0 = [[]]</font></div><div><font face="courier new, monospace">sumsTo1 n = rec sumsTo1 n</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">-- Dynamic (corecursive)</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">sumsTo2 :: Int -> [[Int]]</font></div><div><font face="courier new, monospace">sumsTo2 n = lookup Map.! n</font></div><div><font face="courier new, monospace"> where</font></div><div><font face="courier new, monospace"> lookup = go 1 (Map.singleton 0 [[]])</font></div><div><font face="courier new, monospace"> go m acc | m > n = acc</font></div><div><font face="courier new, monospace"> | otherwise = go (m + 1) (Map.insert m (rec (acc Map.!) m) acc)</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">-- Dynamic (lazy)</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">sumsTo3 :: Int -> [[Int]]</font></div><div><font face="courier new, monospace">sumsTo3 n = lookup Vec.! n</font></div><div><font face="courier new, monospace"> where</font></div><div><font face="courier new, monospace"> lookup = generate (n + 1) $ \m -> </font></div><div><font face="courier new, monospace"> if m == 0 </font></div><div><font face="courier new, monospace"> then [[]] </font></div><div><font face="courier new, monospace"> else rec (lookup Vec.!) m</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">main = do</font></div><div><font face="courier new, monospace"> let a = sumsTo1 10</font></div><div><font face="courier new, monospace"> b = sumsTo2 10</font></div><div><font face="courier new, monospace"> c = sumsTo3 10</font></div><div><font face="courier new, monospace"> print (a == b && b == c)</font></div><div><font face="courier new, monospace"> print a</font></div></div><div><br></div><div>In case the formatting is messed up, see</div><div><a href="https://gist.github.com/wyager/7daebb351d802bbb2a624b71c0f343d3">https://gist.github.com/wyager/7daebb351d802bbb2a624b71c0f343d3</a><br></div></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, May 18, 2019 at 10:15 PM Magicloud Magiclouds <<a href="mailto:magicloud.magiclouds@gmail.com">magicloud.magiclouds@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Thanks. This is kind like my original (did not get through) thought.<br>
<br>
On Sat, May 18, 2019 at 8:25 PM Thorkil Naur <<a href="mailto:naur@post11.tele.dk" target="_blank">naur@post11.tele.dk</a>> wrote:<br>
><br>
> Hello,<br>
><br>
> On Sat, May 18, 2019 at 12:33:00PM +0800, Magicloud Magiclouds wrote:<br>
> > ...<br>
> > 1 - 9, nine numbers. Show all the possible combinations that sum up to<br>
> > 10. Different orders are counted as the same.<br>
> ><br>
> > For example, [1, 4, 5].<br>
><br>
> With<br>
><br>
> sumIs n [] = if n == 0 then [[]] else []<br>
> sumIs n (x:xs)<br>
> = (if n < x then<br>
> []<br>
> else<br>
> map (x:) $ sumIs (n-x) xs<br>
> )<br>
> ++ sumIs n xs<br>
><br>
> we can do:<br>
><br>
> Prelude Main> sumIs 10 [1..9]<br>
> [[1,2,3,4],[1,2,7],[1,3,6],[1,4,5],[1,9],[2,3,5],[2,8],[3,7],[4,6]]<br>
><br>
> > ...<br>
><br>
> Best<br>
> Thorkil<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div>