Newest at the top
| 2024-05-16 18:56:01 +0200 | neiluj | (~neiluj@193.203.71.162) (Ping timeout: 256 seconds) |
| 2024-05-16 18:54:53 +0200 | <Guest13> | if you can do it |
| 2024-05-16 18:54:47 +0200 | <Guest13> | bottom up is usually better surely |
| 2024-05-16 18:54:39 +0200 | <Guest13> | ah I see |
| 2024-05-16 18:53:48 +0200 | <ski> | yea. if you do `fib n = fibLoop 0 1 n where fibLoop a b 0 = a; fibLoop a !b n = fibLoop b (a + b) (n-1)', then that's bottom-up (but keeping just the last two results around, since for fibonacci we know we don't need any previous ones any longer) |
| 2024-05-16 18:52:58 +0200 | <Guest13> | but not other cases |
| 2024-05-16 18:52:51 +0200 | <Guest13> | what is an example of bottom up, I know bottom up parsing where you look at "leaves" of the grammar and then say this must be this production rule and so on |
| 2024-05-16 18:51:59 +0200 | <ski> | (and those are then cached, so that if they're needed in a sibling branch of the call-tree, they won't be recomputed, but just looked up) |
| 2024-05-16 18:51:54 +0200 | <Guest13> | ok so fib (n-1) + fib (n-2) is top down |
| 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 |