purescript/purescript-lists

Efficiency question for snoc

guygastineau opened this issue · 9 comments

guygastineau commented

purescript-lists/src/Data/List.purs

Line 197 in 03a480b

snoc xs x = reverse (x : reverse xs)

Is there a reason that this has to be O(2n)?

In Scheme I often implement things that would translate to this:

snoc xs x = foldr (:) (x : Nil) xs

Unless we need to be really worried about recursion depth in the browsers (maybe we do IDK) This gets it done in O(n).

Anyway, I am just starting to try purescript as of Today, but coming from Haskell and Scheme I am reading a lot of the library sources. Let me know if you all would like this a s a PR.

Cheers

guygastineau commented

Update. I haven't learned how to do benchmarks in purescript yet, but using a stopwatch I was able to beat the built in snoc by about 1 1/2 seconds on the following calculation:

snoc (0..5000000) 0
-- versus
-- toEnd xs x = foldr (:) (x : Nil) xs
toEnd (0..5000000) 0
natefaubion commented

Unless we need to be really worried about recursion depth in the browsers (maybe we do IDK) This gets it done in O(n).

Yes, this is why it is implemented this way. foldr is not stack safe.

guygastineau commented

Interesting. Well, too bad. I guess I should close this issue...

guygastineau commented

Actually it looks like I was pointed to an old version when I clicked the link to the source code. My suggestion is actually the current implementation 🤣

guygastineau commented

I don't know who is in charge of that, but I just looked at a more recent commit and saw my suggested O(n) solution for snoc.

Is it because the new work I am seeing on master hasn't made it to a release tag yet?

guygastineau commented

Okay Nevermind I finally realized that I could change the version of the language in the docs. Have a nice evening

hdgarrood commented

No, it is because you are looking at an old version in Pursuit. See eg https://pursuit.purescript.org/packages/purescript-lists/5.4.0/docs/Data.List#v:snoc

  • 👍1
guygastineau commented

@hdgarrood yes thank you. That is what I had found out by the time I made my last rather vague comment 😂

This is a neat project. I am about to start some front end developement at work, and I am glad that purescript exists.

Elm feels like I am fighting the language, so purs is like a god send.

Anyway, I will continue to see if I can give back to the community (hopefully I will be referencing the current source code next time 🤣)

  • ❤️2