Newest at the top
2024-05-16 19:03:56 +0200 | <ski> | that example makes sense to you ? |
2024-05-16 19:03:31 +0200 | <ski> | this will call `reverse' on the input `[2,3,5,7]', before trying to match it with the pattern `x:_'. so we actually match the list `[7,5,3,2]' with the pattern `x:_', so `x' becomes `7' |
2024-05-16 19:02:54 +0200 | <lambdabot> | 7 |
2024-05-16 19:02:52 +0200 | <ski> | > let last (reverse -> x:_) = x in last [2,3,5,7] |
2024-05-16 19:02:31 +0200 | <ski> | e.g. |
2024-05-16 19:02:24 +0200 | <ski> | my use of the view pattern above is rather unusual .. normally view patterns are used in function (formal) parameter patterns |
2024-05-16 19:02:12 +0200 | <Guest13> | we are assigning a function to the left |
2024-05-16 19:01:50 +0200 | <Guest13> | I don't understand the assignment |
2024-05-16 19:01:50 +0200 | <ski> | `(<expr> -> <pat>)' is a, so-called, view pattern |
2024-05-16 19:01:23 +0200 | <ski> | Guest13 : well, basically we just splice a memoization/caching lookup inbetween each recursive call |
2024-05-16 19:01:13 +0200 | <Guest13> | ((!) . tabulate (0,n) -> fib) = \case 0 -> 0; 1 -> 1; n -> fib (n-1) + fib (n-2) I don't understand |
2024-05-16 19:00:42 +0200 | <ski> | Guest13 : "bottom up is usually better surely","if you can do it" -- depends. if you know which results will be needed, beforehand, i'll probably be a little more efficient, i suppose. but if there may be large swathes of subresults that may not actually be needed, then it's hard to avoid computing them anyway with bottom-up, so in that case you may be doing quite a bit more work than for top-down |
2024-05-16 19:00:39 +0200 | <Guest13> | not sure I understand this one |
2024-05-16 18:58:37 +0200 | <lambdabot> | 144 |
2024-05-16 18:58:35 +0200 | <ski> | > let memoFib n | n >= 0 = fib n where (memoArray (0,n) -> fib) = \case 0 -> 0; 1 -> 1; n -> fib (n-1) + fib (n-2) in memoFib 12 -- same thing, just slightly clearer |
2024-05-16 18:58:19 +0200 | <lambdabot> | Defined. |
2024-05-16 18:58:18 +0200 | <ski> | @let memoArray :: Ix i => (i,i) -> (i -> e) -> (i -> e); memoArray ix f = (L.tabulate ix f !) |
2024-05-16 18:57:30 +0200 | <ski> | ^ a cute way to, instead of inlining the function `fib' into the array `fibs', inlining the array `fibs' into the function `fib', using `ViewPatterns' to pass the function `\case ...' through `L.tabulate (0,n)' (giving back an array), and then also through `(!)' (indexing the array, giving back a function), before naming that function `fib' .. while `\case ...' already uses that `fib', recursively |
2024-05-16 18:57:28 +0200 | <lambdabot> | 144 |
2024-05-16 18:57:26 +0200 | <ski> | > let memoFib n | n >= 0 = fib n where ((!) . L.tabulate (0,n) -> fib) = \case 0 -> 0; 1 -> 1; n -> fib (n-1) + fib (n-2) in memoFib 12 |
2024-05-16 18:57:21 +0200 | <Guest13> | is it convention to put the changing values in the recursive call before or after the static ones? |
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 |