Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Rust vs. Haskell

serokell.io

Post reply on HN
Print view View original

11–20 of 189 posts

Re: Rust vs. Haskell

#11

Post by api »

rkangel wrote: post #10
vlovich123 wrote: post #8

> if we have a map and want to do some operation on a slightly modified map, we can have a value that keeps the old map but also works with the new map (without much performance cost). What black magic is this? Is the article just glossing over the cost of a copy or does Haskell do something weird here to avoid the copy while retaining both versions?

I don't know about Haskell particularly but the underlying implementation of data structures in pure languages is sometimes more complicated to enable this sort of thing. For example, the new updated copy of the map may refer to the "old" map for most of its data, thereby making it cheap to have both.

So copy-on-write basically?

Re: Rust vs. Haskell

#12

Post by ghostwriter »

vlovich123 wrote: post #8

> if we have a map and want to do some operation on a slightly modified map, we can have a value that keeps the old map but also works with the new map (without much performance cost). What black magic is this? Is the article just glossing over the cost of a copy or does Haskell do something weird here to avoid the copy while retaining both versions?

> What black magic is this?

https://en.wikipedia.org/wiki/Persistent_data_structure

Re: Rust vs. Haskell

#13

Post by thedataangel »

vlovich123 wrote: post #8

> if we have a map and want to do some operation on a slightly modified map, we can have a value that keeps the old map but also works with the new map (without much performance cost). What black magic is this? Is the article just glossing over the cost of a copy or does Haskell do something weird here to avoid the copy while retaining both versions?

The second. Because everything in Haskell is immutable, it can take a _lot_ of liberties in terms of letting structures share parts of one another, in the case where one version is derived from the other.

Conversely, in the case where something like a list is modified in entirety (e.g. with a `map` function), if the compiler can determine that the original is no longer needed, it can run the map operation in place - much like you might do on an array in C - avoiding the need for a second copy of the structure in-memory.

Re: Rust vs. Haskell

#14

Post by hgsgm »

vlovich123 wrote: post #8

> if we have a map and want to do some operation on a slightly modified map, we can have a value that keeps the old map but also works with the new map (without much performance cost). What black magic is this? Is the article just glossing over the cost of a copy or does Haskell do something weird here to avoid the copy while retaining both versions?

The wording is terrible, but the simple common Haskell way is to use overlays/diffs.

You have an object. When you want to apply a patch, you create a new object that contains just your patch, plus a reference to the old obejct. DiffArray is the simple common example. It's fast enough when the diffs are small, but terrible when there are many diffs in series, creating a deep stack of references.

It's not obscure. $PATH and the /bin,/usr/bin, /usr/local/bin, $HOME/bin dirs on Linux work the same way.

Re: Rust vs. Haskell

#15

Post by capableweb »

vlovich123 wrote: post #8

> if we have a map and want to do some operation on a slightly modified map, we can have a value that keeps the old map but also works with the new map (without much performance cost). What black magic is this? Is the article just glossing over the cost of a copy or does Haskell do something weird here to avoid the copy while retaining both versions?

> In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. The term was introduced in Driscoll, Sarnak, Sleator, and Tarjans' 1986 article. (Making Data Structures Persistent - https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133...)

From https://en.wikipedia.org/wiki/Persistent_data_structure

Clojure leverages the same data structure for (at least) four basic types; list, map, vector and set, and the following article explains it well with a pretty graph/picture too: https://practical.li/clojurescript/clojure-syntax/persistent...

Re: Rust vs. Haskell

#16

Post by hgsgm »

api wrote: post #11
rkangel wrote: post #10

Earlier quoted context omitted.

I don't know about Haskell particularly but the underlying implementation of data structures in pure languages is sometimes more complicated to enable this sort of thing. For example, the new updated copy of the map may refer to the "old" map for most of its data, thereby making it cheap to have both.

So copy-on-write basically?

No, there is no "write" because the old value never chnages. It's "create an overlay on write"

Re: Rust vs. Haskell

#17

Post by hgsgm »

Joker_vD wrote: post #4

let nums = take 10000000 naturals print $ (sum nums, length nums) > Because the nums list is used for both sum and length computations, the compiler can’t discard list elements until it evaluates both. Now that makes me wonder, if I write something like print $ (sum (take 10000000 naturals), length (take 10000000 naturals)) will it run in constant memory? I think it ought to, but are there mechanisms in GHC optimizer…

It's both solvable and easy to accidentally have blowups by accident.

Re: Rust vs. Haskell

#19

Post by arc-in-space »

api wrote: post #11
rkangel wrote: post #10

Earlier quoted context omitted.

I don't know about Haskell particularly but the underlying implementation of data structures in pure languages is sometimes more complicated to enable this sort of thing. For example, the new updated copy of the map may refer to the "old" map for most of its data, thereby making it cheap to have both.

So copy-on-write basically?

Copy-on-write generally refers to copying everything on every write; this is a persistent data structure, which can do updates while only copying a small part of itself. Same purpose as COW, but more efficient for larger data structures we want to make lots of small updates on.

Re: Rust vs. Haskell

#20

Post by Joker_vD »

api wrote: post #11
rkangel wrote: post #10

Earlier quoted context omitted.

I don't know about Haskell particularly but the underlying implementation of data structures in pure languages is sometimes more complicated to enable this sort of thing. For example, the new updated copy of the map may refer to the "old" map for most of its data, thereby making it cheap to have both.

So copy-on-write basically?

Well, yeah, only there ain't any writes (and therefore, no copying).

The simplest example would be with linked lists, I suppose: you have a list A->B->C, then you take the B->C sublist and prepend X to it, so you now have X->B->C, but A->B->C is still around, and "B->C" part is shared between those.

Post reply on HN