Newest at the top
2024-05-16 18:51:26 +0200 | <ski> | top-down means that you start at the top desired result, and then let demand determine which sub-results are actually demanded |
2024-05-16 18:51:01 +0200 | <ski> | it requires knowing which results will depend on which other results, so that you can make sure to initialize the latter results before the former ones need them |
2024-05-16 18:50:55 +0200 | <Guest13> | and then back up to the top |
2024-05-16 18:50:51 +0200 | <Guest13> | and then work your way down to the bottom |
2024-05-16 18:50:43 +0200 | <Guest13> | but when you call it you start at the top? |
2024-05-16 18:50:16 +0200 | <ski> | bottom-up means that you start at the "base cases" of the recursion, building your way upwards. for fibonacci, this would be starting at `0' and `1' |
2024-05-16 18:49:52 +0200 | <Guest13> | I know one goes from leaves other from root but idk |
2024-05-16 18:49:40 +0200 | <Guest13> | I can never get top down vs bottom up lol |
2024-05-16 18:49:25 +0200 | <ski> | it automatically gives you top-down dynamic programming, through lazy caching of the array elements |
2024-05-16 18:49:03 +0200 | <Guest13> | yeah I like it |
2024-05-16 18:48:58 +0200 | <ski> | it's just a recursivelt defined array |
2024-05-16 18:48:46 +0200 | <Guest13> | "where fibs = L.tabulate (0,n) (\n -> case n of 0 -> 0; 1 -> 1; n -> fibs ! (n - 1) + fibs ! (n - 2))" is crazy |
2024-05-16 18:48:40 +0200 | <ski> | (`listArray' is for when you just want to list the array elements (in proper index enumeration order, as given by e.g. `range'. `array' allows you to give the elements in arbitrary order, but then you have to pair up each element with its corresponding index, and it's also possible to repeat an index (in which case, iirc, it will just pick the last association pair)) |
2024-05-16 18:47:16 +0200 | <lambdabot> | Ix i => (i, i) -> [(i, e)] -> Array i e |
2024-05-16 18:47:15 +0200 | <ski> | @type array |
2024-05-16 18:47:09 +0200 | <lambdabot> | Ix i => (i, i) -> [e] -> Array i e |
2024-05-16 18:47:08 +0200 | <ski> | @type listArray |
2024-05-16 18:47:00 +0200 | <ski> | .. and `tabulate' calls `listArray' with a list defined using `range' to generate elements for all valid indices |
2024-05-16 18:46:21 +0200 | <ski> | that's all indices in a rectangle, with upper left corner `(0,0)', lower right corner `(1,3)' |
2024-05-16 18:46:08 +0200 | <Guest13> | I see |
2024-05-16 18:46:05 +0200 | hueso | (~root@user/hueso) |
2024-05-16 18:45:56 +0200 | <lambdabot> | Ix a => (a, a) -> [a] |
2024-05-16 18:45:55 +0200 | <ski> | @type range |
2024-05-16 18:45:45 +0200 | <lambdabot> | [(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(1,3)] |
2024-05-16 18:45:44 +0200 | <ski> | > range ((0,0),(1,3)) |
2024-05-16 18:45:20 +0200 | <ski> | (there are instances like `(Ix a,Ix b,Ix c) => Ix (a,b,c)') |
2024-05-16 18:44:55 +0200 | hueso | (~root@user/hueso) (Read error: Connection reset by peer) |
2024-05-16 18:43:30 +0200 | <ski> | the above should work |
2024-05-16 18:39:44 +0200 | <Guest13> | do I need to define my own 3d tabulate? |
2024-05-16 18:37:48 +0200 | <Guest13> | I will try this now thank you for the help ski |
2024-05-16 18:37:05 +0200 | <Guest13> | I think I get it though, my program will query 0 0 0 in the table which will spawn recursive calls and the base case is n m 0 = 1 |
2024-05-16 18:35:55 +0200 | <Guest13> | yeah, for some reason it being in a table confused me |
2024-05-16 18:35:53 +0200 | euphores | (~SASL_euph@user/euphores) |
2024-05-16 18:35:38 +0200 | tzh | (~tzh@c-76-115-131-146.hsd1.or.comcast.net) |
2024-05-16 18:35:20 +0200 | <mauke> | dead ends are where the recursion dies :-) |
2024-05-16 18:35:09 +0200 | <Guest13> | this would be setting the value to 0 |
2024-05-16 18:34:55 +0200 | <ski> | base cases / dead ends, i guess |
2024-05-16 18:33:11 +0200 | <Guest13> | and you have some calls where you say it has gone wrong and ways = 0 |
2024-05-16 18:32:56 +0200 | <Guest13> | its basically a "ways if go left" + "ways if go right" recursion |
2024-05-16 18:32:25 +0200 | <Guest13> | I need to think about how to implement the "dead ends" of the recursive call |
2024-05-16 18:32:10 +0200 | <Guest13> | I will have a go at this |
2024-05-16 18:31:37 +0200 | <ski> | (i guess you actually meant `f x (y-1) z + f (x-1) y z', btw) |
2024-05-16 18:30:11 +0200 | <Guest13> | im trying to count the ways of doing something |
2024-05-16 18:29:25 +0200 | <Guest13> | I think I get how to do it |
2024-05-16 18:29:20 +0200 | euphores | (~SASL_euph@user/euphores) (Quit: Leaving.) |
2024-05-16 18:28:58 +0200 | <Guest13> | so I can do a \(x,y,z) -> f x y-1 z + f x-1 y z |
2024-05-16 18:28:54 +0200 | <ski> | oh, you said "yes, but I am probably framing it badly" just after i asked "are you sure dynamic programming would make sense, for your problem, then ?", so i was taking that for granted |
2024-05-16 18:28:06 +0200 | <ski> | you can use `listArray' (or `array'), or the `tabulate' i defined above, to (lazily) populate the array with elements, based on their indices |
2024-05-16 18:28:03 +0200 | <Guest13> | im not really doing dp |
2024-05-16 18:27:57 +0200 | <Guest13> | I understand the map f [1..] for fib, and even the tabulate version you showed me but I don't understand this one |