Newest at the top
| 2025-01-28 22:57:31 +0100 | sawilagar | (~sawilagar@user/sawilagar) (Ping timeout: 252 seconds) |
| 2025-01-28 22:57:02 +0100 | Midjak | (~MarciZ@82.66.147.146) (Quit: This computer has gone to sleep) |
| 2025-01-28 22:56:39 +0100 | merijn | (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 260 seconds) |
| 2025-01-28 22:55:44 +0100 | tnt2 | tnt1 |
| 2025-01-28 22:55:44 +0100 | tnt1 | (~Thunderbi@user/tnt1) (Ping timeout: 265 seconds) |
| 2025-01-28 22:55:06 +0100 | <c_wraith> | (at least in a non-strict language) |
| 2025-01-28 22:54:58 +0100 | Googulator | (~Googulato@2a01-036d-0106-1666-e945-fd21-b920-9aa7.pool6.digikabel.hu) (Client Quit) |
| 2025-01-28 22:54:48 +0100 | <c_wraith> | monochrom: paramorphisms can be an efficiency win, even if they have the same computational power as catamorphisms. |
| 2025-01-28 22:53:55 +0100 | <tomsmeding> | :) |
| 2025-01-28 22:53:38 +0100 | <haskellbridge> | <thirdofmay18081814goya> thanks a lot for the example! |
| 2025-01-28 22:53:33 +0100 | <tomsmeding> | to do better in terms of space usage, you'll have to augment the folder |
| 2025-01-28 22:53:33 +0100 | <haskellbridge> | <thirdofmay18081814goya> hm I see |
| 2025-01-28 22:53:16 +0100 | <tomsmeding> | goya: note that my code has to reconstruct the tree in the fold, even though there is already one in memory: the one we're folding over. So this returns new copies of each subtree instead of shared subtrees |
| 2025-01-28 22:53:10 +0100 | <int-e> | strictly awful? |
| 2025-01-28 22:52:42 +0100 | tnt2 | (~Thunderbi@user/tnt1) tnt1 |
| 2025-01-28 22:52:23 +0100 | <monochrom> | Oh! To avoid lazy evaluation, just lift to liftA2 (&&) for a suitable Applicative instance. >:) |
| 2025-01-28 22:52:08 +0100 | <tomsmeding> | use Maybe instead of [] to get only the first / last / ... match |
| 2025-01-28 22:52:03 +0100 | <haskellbridge> | <thirdofmay18081814goya> will be studying that example |
| 2025-01-28 22:52:00 +0100 | <haskellbridge> | <thirdofmay18081814goya> oh neat |
| 2025-01-28 22:51:38 +0100 | merijn | (~merijn@host-vr.cgnat-g.v4.dfn.nl) merijn |
| 2025-01-28 22:51:32 +0100 | <monochrom> | Stops early. |
| 2025-01-28 22:51:31 +0100 | <c_wraith> | Yeah, you don't need to work for that. You need to work to avoid it. |
| 2025-01-28 22:51:27 +0100 | <lambdabot> | False |
| 2025-01-28 22:51:25 +0100 | <monochrom> | > foldr (&&) undefined (False : undefined) |
| 2025-01-28 22:51:15 +0100 | <tomsmeding> | what monochrom says |
| 2025-01-28 22:51:08 +0100 | <monochrom> | Lazy evaluation easily stops early when something is found. |
| 2025-01-28 22:51:05 +0100 | <tomsmeding> | goya: https://play.haskell.org/saved/KMCLVKww |
| 2025-01-28 22:50:47 +0100 | Googulator | (~Googulato@2a01-036d-0106-1666-e945-fd21-b920-9aa7.pool6.digikabel.hu) |
| 2025-01-28 22:50:36 +0100 | <haskellbridge> | <thirdofmay18081814goya> i.e., the challenge is to use one of the fixpoints of the datastructure to recurse structurally, and have a way to stop the recursion |
| 2025-01-28 22:50:12 +0100 | Googulator | (~Googulato@2a01-036d-0106-1666-e945-fd21-b920-9aa7.pool6.digikabel.hu) (Quit: Client closed) |
| 2025-01-28 22:49:42 +0100 | <monochrom> | Data.Tree has a foldTree. I believe that it is sufficient for looking for a node by label. I don't really care about other recursion schemes, they are sociology not math. |
| 2025-01-28 22:49:38 +0100 | <haskellbridge> | <thirdofmay18081814goya> and as we fold there's no way to stop with just a fold |
| 2025-01-28 22:49:17 +0100 | <haskellbridge> | <thirdofmay18081814goya> well the issue is we expect a tree to be returned |
| 2025-01-28 22:48:32 +0100 | <int-e> | Anyway, this sounds like it's just matching the keys at each node so the natural fold foldTree :: b -> (a -> b -> b -> b) -> Tree a -> b should work just fine for this. Unless you want it to be efficient, in which case it becomes a data structure problem where you probably want some more bookkeeping that track keys and associated subtrees. |
| 2025-01-28 22:47:47 +0100 | <c_wraith> | I still don't actually understand the underlying data structure. I just know how to detect divergences from the code in the paper. |
| 2025-01-28 22:47:35 +0100 | peterbecich | (~Thunderbi@syn-047-229-123-186.res.spectrum.com) peterbecich |
| 2025-01-28 22:46:21 +0100 | <c_wraith> | for anyone following along, both the psqueues and PSQueue packages now have releases with my tree-balancing fix in them, so they no longer decay to O(n) operations after a long sequence of monotonic inserts |
| 2025-01-28 22:46:04 +0100 | michalz | (~michalz@185.246.207.193) (Remote host closed the connection) |
| 2025-01-28 22:45:52 +0100 | <haskellbridge> | <thirdofmay18081814goya> this constraint might limit what sort of match or order we might be able to get |
| 2025-01-28 22:45:50 +0100 | <int-e> | A source of confusion here is that strings can be concatenated. So "matching" grows some extra dimensions of freedom. |
| 2025-01-28 22:45:46 +0100 | <tomsmeding> | you probably can |
| 2025-01-28 22:45:24 +0100 | <haskellbridge> | <thirdofmay18081814goya> determining whether you can solve this with a catamorphism |
| 2025-01-28 22:45:08 +0100 | <tomsmeding> | what's the X problem here? |
| 2025-01-28 22:45:00 +0100 | <tomsmeding> | you first have to decide what you _want_ :p |
| 2025-01-28 22:44:53 +0100 | <haskellbridge> | <thirdofmay18081814goya> with any match |
| 2025-01-28 22:44:51 +0100 | <tomsmeding> | is this even valid? |
| 2025-01-28 22:44:41 +0100 | <haskellbridge> | <thirdofmay18081814goya> as a first approximation i'd be interested in any method that does this in any order |
| 2025-01-28 22:44:40 +0100 | <tomsmeding> | if you bave `Node "a" (Node "b" (Node "c" Nil Nil) Nil) (Node "b" (Node "d" Nil Nil) Nil)`, and you search for "b", which of the two matching subtrees do you want? |
| 2025-01-28 22:43:49 +0100 | Square | (~Square@user/square) (Ping timeout: 248 seconds) |
| 2025-01-28 22:43:45 +0100 | <haskellbridge> | <thirdofmay18081814goya> i meant if it matches "Node nodeString _ _" and "nodeString = givenString" |