3 ms·

Slightly off-topic but what's a good forum to seek help on FP practices outside of the courses like this online? Every winter break I get back into trying to l

Slightly off-topic but what's a good forum to seek help on FP practices outside of the courses like this online? Every winter break I get back into trying to learn more FP (in Haskell) and in the past several years I have been practicing algo problems (codeforces, advent of code, leetcode). I always get stuck on more advanced graph algorithms where you traverse a and modify a graph, not a tree structure - it gets particularly tricky to work on circular data structures (I learned about "tying the knot" but it's incredibly challenging for me) and usually the runtime perf is sub-par both asymptotically and empirically.

deleted 3y ago
[deleted]
low_tech_punk 3y ago
My Scala friends heavily rely on discord, e.g. the one mentioned here: https://typelevel.org/blog/2021/05/05/discord-migration.html https://typelevel.org/blog/2021/05/05/discord-migration.html It is language based community but they do have vibrant discussion on learning and theories.
kccqzy 3y ago
Many graph algorithms are designed for imperative programming. It's safe to say that functional graph programming is still in its infancy. Alga[0], a system for algebraic graphs only came out in 2017. And efficient algorithms for graphs may yet to be discovered (even something as simple as reversing a list that's both efficient and elegant only came out in 1986!) That said, as a beginner in functional programming, it would probably be good enough if you just focus on directly translating imperative graph algorithms to functional programming. You simply solve the problem by programming at a slightly lower level of abstraction. [0]: https://dl.acm.org/authorize?N46678 https://dl.acm.org/authorize?N46678 or preprint at https://github.com/snowleopard/alga-paper/releases/download/icfp-submission-archived/alga.pdf https://github.com/snowleopard/alga-paper/releases/download/...
- philsnow 3y ago
  I don't know if [0] would be any help, it doesn't talk about graphs in particular but does talk about functional-focused approaches to data structures. This note[1] on the wikipedia page for the book says it better than I could: > [...] consider a function that accepts a mutable list, removes the first element from the list, and returns that element. In a purely functional setting, removing an element from the list produces a new and shorter list, but does not update the original one. In order to be useful, therefore, a purely functional version of this function is likely to have to return the new list along with the removed element. In the most general case, a program converted in this way must return the "state" or "store" of the program as an additional result from every function call. Such a program is said to be written in store-passing style. [0] https://www.cs.cmu.edu/~rwh/students/okasaki.pdf https://www.cs.cmu.edu/~rwh/students/okasaki.pdf [1] https://en.wikipedia.org/wiki/Purely_functional_data_structure#Using_purely_functional_data_structures https://en.wikipedia.org/wiki/Purely_functional_data_structu...
  - imslavko 3y ago
    Oh yeah, a pure function that accepts previous state, and returns the new state is the pattern I use a lot. The issue is that it is hard to do on complex graph structures in an algorithm where incremental changes happen to the graph O(n) times - it ends up creating complex code and complex execution that might be slow to pass the time limit on Codeforces, let's say. In the OCaml world maybe this is the place where you say "screw it, this abstracted function does some stateful temporary business, but it looks pure from the outside" but in Haskell it's a lot harder to pull off without going deep into monads (and I forget how those work every time).
    - kccqzy 3y ago
      Oh definitely go deep into monads. If you use the ST monad to do mutations, some people think Haskell provides nicer syntax to do imperative programming than traditional imperative languages like C. But of course such nicer syntax only comes from understanding and using important abstractions like monads, foldable, or traversable. Then there are niceties like automatic SoA/AoS transformation using type families.

deleted 3y ago

[deleted]

low_tech_punk 3y ago

My Scala friends heavily rely on discord, e.g. the one mentioned here: https://typelevel.org/blog/2021/05/05/discord-migration.html https://typelevel.org/blog/2021/05/05/discord-migration.html It is language based community but they do have vibrant discussion on learning and theories.

kccqzy 3y ago

Many graph algorithms are designed for imperative programming. It's safe to say that functional graph programming is still in its infancy. Alga[0], a system for algebraic graphs only came out in 2017. And efficient algorithms for graphs may yet to be discovered (even something as simple as reversing a list that's both efficient and elegant only came out in 1986!) That said, as a beginner in functional programming, it would probably be good enough if you just focus on directly translating imperative graph algorithms to functional programming. You simply solve the problem by programming at a slightly lower level of abstraction. [0]: https://dl.acm.org/authorize?N46678 https://dl.acm.org/authorize?N46678 or preprint at https://github.com/snowleopard/alga-paper/releases/download/icfp-submission-archived/alga.pdf https://github.com/snowleopard/alga-paper/releases/download/...

philsnow 3y ago
I don't know if [0] would be any help, it doesn't talk about graphs in particular but does talk about functional-focused approaches to data structures. This note[1] on the wikipedia page for the book says it better than I could: > [...] consider a function that accepts a mutable list, removes the first element from the list, and returns that element. In a purely functional setting, removing an element from the list produces a new and shorter list, but does not update the original one. In order to be useful, therefore, a purely functional version of this function is likely to have to return the new list along with the removed element. In the most general case, a program converted in this way must return the "state" or "store" of the program as an additional result from every function call. Such a program is said to be written in store-passing style. [0] https://www.cs.cmu.edu/~rwh/students/okasaki.pdf https://www.cs.cmu.edu/~rwh/students/okasaki.pdf [1] https://en.wikipedia.org/wiki/Purely_functional_data_structure#Using_purely_functional_data_structures https://en.wikipedia.org/wiki/Purely_functional_data_structu...
- imslavko 3y ago
  Oh yeah, a pure function that accepts previous state, and returns the new state is the pattern I use a lot. The issue is that it is hard to do on complex graph structures in an algorithm where incremental changes happen to the graph O(n) times - it ends up creating complex code and complex execution that might be slow to pass the time limit on Codeforces, let's say. In the OCaml world maybe this is the place where you say "screw it, this abstracted function does some stateful temporary business, but it looks pure from the outside" but in Haskell it's a lot harder to pull off without going deep into monads (and I forget how those work every time).
  - kccqzy 3y ago
    Oh definitely go deep into monads. If you use the ST monad to do mutations, some people think Haskell provides nicer syntax to do imperative programming than traditional imperative languages like C. But of course such nicer syntax only comes from understanding and using important abstractions like monads, foldable, or traversable. Then there are niceties like automatic SoA/AoS transformation using type families.