Logs: freenode/#haskell
| 2021-03-14 09:48:43 | <lambdabot> | [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17... |
| 2021-03-14 09:50:03 | <ephemient> | @where pristine.hs |
| 2021-03-14 09:50:03 | <lambdabot> | I know nothing about pristine.hs. |
| 2021-03-14 09:50:06 | <MoeEl> | I tried to do heapsort in Haskell, 3 days after learning it, now I have gray hair |
| 2021-03-14 09:50:14 | <ephemient> | eh, I forgot if lambdabot imports Linear |
| 2021-03-14 09:50:21 | <Rembane> | MoeEl: What gives you gray hairs? Where do you get stuck? |
| 2021-03-14 09:50:26 | <ephemient> | :t Linear.Matrix.M22 |
| 2021-03-14 09:50:27 | <lambdabot> | error: |
| 2021-03-14 09:50:27 | <lambdabot> | Not in scope: data constructor ‘Linear.Matrix.M22’ |
| 2021-03-14 09:50:27 | <lambdabot> | No module named ‘Linear.Matrix’ is imported. |
| 2021-03-14 09:51:40 | → | malumore joins (~malumore@151.62.115.237) |
| 2021-03-14 09:52:01 | <MoeEl> | Not really stuck. I got it done, but it’s so inefficient because of the immutability of lists. I looked up MArray but it seems horrible. Then just learned about the vector package, so I think that will be my next experiment |
| 2021-03-14 09:52:29 | <Rembane> | MoeEl: How is it inefficient? |
| 2021-03-14 09:53:34 | <tomsmeding> | Rembane: heapsort is defined in terms of swapping operations on an array |
| 2021-03-14 09:54:22 | <MoeEl> | Rembane anytime I need to swap two elements I have to construct a new list, for now I’m using drop and take which is O(n) when swapping is supposed to be O(1) |
| 2021-03-14 09:55:03 | <ephemient> | array and vector have similar operations, vector is more ergonomic to use in lots of ways though |
| 2021-03-14 09:55:22 | × | qih quits (~pi@210-54-120-166.adsl.xtra.co.nz) (Quit: leaving) |
| 2021-03-14 09:55:32 | → | rdivyanshu joins (uid322626@gateway/web/irccloud.com/x-hxnrioewzbkzbjta) |
| 2021-03-14 09:55:32 | × | MoeEl quits (62a7e21a@ip98-167-226-26.ph.ph.cox.net) (Quit: Connection closed) |
| 2021-03-14 09:58:49 | → | MoeEl joins (62a7e21a@ip98-167-226-26.ph.ph.cox.net) |
| 2021-03-14 09:59:28 | <MoeEl> | Got disconnected. Hope I didn’t miss any responses |
| 2021-03-14 09:59:34 | × | hiptobecubic quits (~john@unaffiliated/hiptobecubic) (Ping timeout: 260 seconds) |
| 2021-03-14 09:59:51 | <tomsmeding> | you didn't :) |
| 2021-03-14 10:00:38 | <tomsmeding> | but yeah Data.Vector.Mutable may be somewhat easier to use than Data.Array.MArray, but they give mostly the same operations |
| 2021-03-14 10:01:11 | <MoeEl> | Any top book recommendations in this channel? |
| 2021-03-14 10:01:23 | <tomsmeding> | 'vector' is special-cased on single-dimensional arrays, whereas 'array' allows any instance of Ix as a key (which includes Int, producing single-dimensional arrays) |
| 2021-03-14 10:02:02 | <curiousgay> | ephemient: have you seen my idea about how to make arrays lazy? I think it's naive, but if it's not and it can be used to represent lists internally without significant tradeoffs in memory and performance, maintainers will have to carefully restructure runtime (I know how restructuring can be hard) |
| 2021-03-14 10:02:09 | <curiousgay> | s/about/above/ |
| 2021-03-14 10:02:26 | × | xff0x quits (~xff0x@2001:1a81:527c:ad00:3e:1651:56e6:1c9) (Ping timeout: 264 seconds) |
| 2021-03-14 10:02:45 | → | hiptobecubic joins (~john@unaffiliated/hiptobecubic) |
| 2021-03-14 10:02:56 | → | xff0x joins (~xff0x@2001:1a81:527c:ad00:2731:c024:969b:283c) |
| 2021-03-14 10:03:28 | <MoeEl> | Maybe I’m thinking it wrong but I liked that you can create a vector from a list. If you worked with Python it’s kinda similar to most packages like numpy or pandas. The syntax for constructing arrays is very prohibitive to me |
| 2021-03-14 10:04:08 | <ephemient> | curiousgay: I think you're looking at a very small subset of what List is used for |
| 2021-03-14 10:04:56 | <ephemient> | curiousgay: (:) means we can cheaply discard any initial portion, have multiple lists share the same tail, have a list use its own tail... like the `fib = 0 : 1 : zipWith (+) fib (tail fibs)` example just now |
| 2021-03-14 10:04:58 | <curiousgay> | ephemient: and you are right, because I am reading tutorial without exercises that introduces basics |
| 2021-03-14 10:05:52 | <tomsmeding> | MoeEl: what about https://hackage.haskell.org/package/array-0.5.4.0/docs/Data-Array-MArray.html#v:newListArray ? |
| 2021-03-14 10:06:11 | <tomsmeding> | fromList' l = newListArray (0, length l - 1) l |
| 2021-03-14 10:06:14 | × | lambda-11235 quits (~lambda-11@2600:1700:7c70:4600:f419:51eb:6249:5266) (Quit: Bye) |
| 2021-03-14 10:06:31 | <tomsmeding> | (which produces the result in a monad, of course, because mutable arrays; the non-mutable version doesn't have monads) |
| 2021-03-14 10:06:38 | <ephemient> | it is possible to build something like an lazy infinite Sequence with O(log n) indexed access, but that doesn't strike me as particularly useful |
| 2021-03-14 10:08:20 | <ephemient> | (I mean, it has its uses; that's how some Haskell memoization libraries work. but it doesn't have as many general uses as [] I believe) |
| 2021-03-14 10:08:33 | <MoeEl> | I wish they had some examples .. I don’t know what monads are yet 😁 |
| 2021-03-14 10:09:20 | <tomsmeding> | MoeEl: mutable arrays using 'vector' will also use monads :p |
| 2021-03-14 10:09:35 | <curiousgay> | ephemient: your example with fibonacci reminds me Rust's tutorial that tells how to create a structure that'll be evaluated lazingly (not hard to translate to C), I think fib function can implicitly have a global variable that will be updated when needed |
| 2021-03-14 10:09:47 | <tomsmeding> | mutable things in haskell have to use monads in general |
| 2021-03-14 10:10:19 | <curiousgay> | implicitly - I mean how compiler decides internally |
| 2021-03-14 10:10:48 | <MoeEl> | 😭 |
| 2021-03-14 10:10:58 | <tomsmeding> | curiousgay: such a structure would be useful for certain purposes, but the standard list structure also has its uses |
| 2021-03-14 10:11:02 | <MoeEl> | Back to the classroom then |
| 2021-03-14 10:11:06 | <tomsmeding> | please build such a thing, as a separate library :p |
| 2021-03-14 10:11:48 | <curiousgay> | tomsmeding: if internal implementation of compiler can be safely changed, that won't affect language itself |
| 2021-03-14 10:12:38 | <ephemient> | curiousgay: true of course, but you'd have to prove that you can always perform this sort of program rewriting safely |
| 2021-03-14 10:12:48 | <tomsmeding> | MoeEl: it's because everything in haskell is supposed to be immutable. So if you want to have mutable arrays, you should somehow enforce that the programmer cannot observe that the previous value changed under their feet, breaking the immutability principle -- and that's done using monads |
| 2021-03-14 10:12:57 | <tomsmeding> | though monads aren't hard to use! |
| 2021-03-14 10:13:23 | <tomsmeding> | fully understanding how they work under the hood is slightly more work, but just using them is quite doable, also for a beginner |
| 2021-03-14 10:13:27 | <tomsmeding> | don't despair! :) |
| 2021-03-14 10:13:42 | <ephemient> | MoeEl: in theory the newly-merged Linear Types in Haskell would allow for building a mutable vector library without monads. but nobody has done so yet as far as I know, and you'd have to learn about linear types which I don't think is easier... |
| 2021-03-14 10:13:56 | <tomsmeding> | hah yes |
| 2021-03-14 10:15:21 | <Rembane> | tomsmeding, MoeEl: That's a very good point. I mixed heapsort up with mergesort. |
| 2021-03-14 10:16:13 | <curiousgay> | ephemient: yeah, that'll require testing by building different programs, also if most programs use lists in a way that'll work faster with lists, such a change in runtime will only be worth for saving memory |
| 2021-03-14 10:16:18 | <MoeEl> | I sorta understand the reasoning behind it from FP standpoint, but it makes implementing certain algorithms like heapsort slow. But surely my curiosity for monads peaked :) |
| 2021-03-14 10:17:45 | <tomsmeding> | MoeEl: if you don't want to go into mutable arrays, you can use Data.Sequence instead of lists; that structure has O(log(n)) complexity for most operations instead of O(n) as for lists |
| 2021-03-14 10:18:16 | <tomsmeding> | preserving the pattern that converting a traditional imperative algorithm to use immutable structures in haskell introduces an extra log-factor in the time complexity |
| 2021-03-14 10:18:35 | <tomsmeding> | but if you want to avoid also that log factor, then mutable arrays are the thing :) |
| 2021-03-14 10:18:38 | <MoeEl> | Rembane even mergesort suffers the same but at least the sorted list it can be built up from ground rather than split and merged |
| 2021-03-14 10:19:21 | <Rembane> | MoeEl: Yeah, that's true. |
| 2021-03-14 10:19:37 | <tomsmeding> | MoeEl: I believe mergesort can be implemented in O(n * log(n)) in normal, immutable haskell using lists? |
| 2021-03-14 10:20:54 | → | merijn joins (~merijn@83-160-49-249.ip.xs4all.nl) |
| 2021-03-14 10:21:09 | <curiousgay> | ephemient: hm, thinking about that constantly discarding initial portions won't be cheap for memory because garbage collector will have to store entire array and depending on size it might occupy even more memory than a list would |
| 2021-03-14 10:21:12 | <MoeEl> | tomsmeding I believe so. I think rather than splitting the list you just take elements in pairs and combine them. If I understood correctly |
| 2021-03-14 10:22:36 | <MoeEl> | My motivation was to compare Python and Haskell performance of a sort algorithm but I ran into the brick wall. |
| 2021-03-14 10:23:15 | × | jamm_ quits (~jamm@unaffiliated/jamm) (Remote host closed the connection) |
| 2021-03-14 10:23:23 | <siraben> | With linear base, in the future one won't need to use a monad to use the mutable structures right? |
| 2021-03-14 10:23:59 | → | jamm_ joins (~jamm@unaffiliated/jamm) |
| 2021-03-14 10:25:11 | <ephemient> | once somebody writes those linear mutable structures, I would expect |
| 2021-03-14 10:25:17 | <curiousgay> | siraben: what? internally everything after being built is mutable, the purpose of declarative language is to provide abstraction over that |
| 2021-03-14 10:25:59 | <siraben> | curiousgay: sure, but with linear types you can have in-place mutable structures without comprising the reformational transparency Haskell has |
| 2021-03-14 10:26:50 | <siraben> | ephemient: the FAQ on GHC's wiki re linear types says that they won't lead to better performance (as of yet), but would be nice to control Haskell programs to the point where you can guarantee X about of allocations occur and where |
| 2021-03-14 10:27:21 | <siraben> | s/reformational/referential/ |
| 2021-03-14 10:27:22 | <ephemient> | curiousgay: one way of enforcing sequencing of mutations is through monads. another way is through linear types. so far Haskell has the former, and some infrastructure to make the latter possible, but that's just getting started |
| 2021-03-14 10:27:23 | <siraben> | damn spellchecker |
| 2021-03-14 10:28:02 | <siraben> | (reformational transparency would be nice IRL though :P) |
| 2021-03-14 10:28:50 | × | jamm_ quits (~jamm@unaffiliated/jamm) (Ping timeout: 264 seconds) |
| 2021-03-14 10:32:24 | × | MoeEl quits (62a7e21a@ip98-167-226-26.ph.ph.cox.net) (Quit: Ping timeout (120 seconds)) |
| 2021-03-14 10:32:26 | × | borne quits (~fritjof@200116b864d4700065fd8eaafdc5f06e.dip.versatel-1u1.de) (Ping timeout: 264 seconds) |
| 2021-03-14 10:34:24 | → | monadmatt joins (~user@119-17-128-101.771180.mel.nbn.aussiebb.net) |
| 2021-03-14 10:38:39 | × | tzh quits (~tzh@c-24-21-73-154.hsd1.wa.comcast.net) (Quit: zzz) |
| 2021-03-14 10:38:48 | × | monadmatt quits (~user@119-17-128-101.771180.mel.nbn.aussiebb.net) (Ping timeout: 245 seconds) |
| 2021-03-14 10:39:47 | × | tromp quits (~tromp@dhcp-077-249-230-040.chello.nl) (Remote host closed the connection) |
| 2021-03-14 10:40:25 | → | MoeEl joins (62a7e21a@ip98-167-226-26.ph.ph.cox.net) |
| 2021-03-14 10:42:28 | × | kafl_ quits (~kafl@unaffiliated/kafl) (Ping timeout: 260 seconds) |
| 2021-03-14 10:42:33 | ← | MoeEl parts (62a7e21a@ip98-167-226-26.ph.ph.cox.net) () |
| 2021-03-14 10:43:56 | → | tromp joins (~tromp@dhcp-077-249-230-040.chello.nl) |
| 2021-03-14 10:44:00 | × | toorevitimirp quits (~tooreviti@117.182.180.50) (Remote host closed the connection) |
| 2021-03-14 10:44:48 | × | hiptobecubic quits (~john@unaffiliated/hiptobecubic) (Ping timeout: 246 seconds) |
| 2021-03-14 10:45:12 | → | _ht joins (~quassel@82-169-194-8.biz.kpn.net) |
| 2021-03-14 10:46:20 | → | elfets joins (~elfets@ip-37-201-23-96.hsi13.unitymediagroup.de) |
| 2021-03-14 10:54:11 | × | malumore quits (~malumore@151.62.115.237) (Remote host closed the connection) |
| 2021-03-14 10:54:29 | → | malumore joins (~malumore@151.62.115.237) |
| 2021-03-14 10:54:43 | × | stree quits (~stree@68.36.8.116) (Ping timeout: 260 seconds) |
All times are in UTC.