5 ms·

> One thing that has been holding me back is the lack of real world examples. I get demotivated when only solving toy problems. I looked at haskell a few month

> One thing that has been holding me back is the lack of real world examples. I get demotivated when only solving toy problems. I looked at haskell a few months ago and had a similar problem. While I don't mind the toy problems, all those toy problems have something in common... They can be easily solved with recursion. There are probably patterns to deal with other problems and this would have been more interesting to me. I just had to think to myself: "If all you have is recursion every tutorial looks like a parser" ;)

chongli 6y ago
Recursion is equivalent to iteration. You can solve any problem you like with it. The problem with those tutorials is that they’re trying to do two things at once: 1) teach you Haskell and 2) advocate for Haskell. I’m currently working as a full time assistant for one of the first year computer science courses at my university. This course is taught in a teaching dialect of Racket which does not allow mutation or side effects of any kind. That doesn’t stop the profs from creating assignments with real world applicability such as graffiti stroke recognizers and decision tree learning algorithms. The key is that they’re not trying to make Racket look good, so the patterns of recursion can get pretty ugly at times.
- the5avage 6y ago
  > Recursion is equivalent to iteration. You can solve any problem you like with it. Maybe my comment was somehow badly written, because you (and the only other reply from chriswarbo) clearly misunderstood me. I know that recursion is equivalent to iteration^^ My point was that some problems fit the one or the other better. Look at fft for example. The algorithm is easy with recursion but hard with iteration. For other problems its the opposite.
  - tasuki 6y ago
    Which problems are hard to solve with recursion instead of iteration?
    - the5avage 6y ago
      I found something like splitting a string into words not very intuitive... Also the classical (recursive) fibonacci function everyone shows has accidental complexity of O(2^n). If you want a sane version it looks definitely more complicated than the iterative version. I never saw a recursive version of bresenham's line plotting algorithm so this might be a good candidate as well ;)
      - chongli 6y ago
        I found something like splitting a string into words not very intuitive... Just use a couple of accumulators (one for the current word, one for the list of completed words). Also the classical (recursive) fibonacci function everyone shows has accidental complexity of O(2^n). That's moving the goalposts. If you want a really fast fibonacci function then the classical iterative algorithm [which is O(n)] is not what you want either. Better to use matrix exponentiation which you can implement nicely with recursion using a divide-and-conquer approach similar to mergesort, giving you fibonacci with time O(log(n)). I never saw a recursive version of bresenham's line plotting algorithm so this might be a good candidate as well ;) There's nothing special about Bresenham's line algorithm that would make it particularly challenging to implement with recursion.
      - a1369209993 6y ago
        > splitting a string into words not very intuitive It seems okay? split :: String -> [String] split s = w s "" where w [] "" = [] w [] a = [reverse a] w (' ':ss) "" = w ss "" w (' ':ss) a = reverse a : w ss "" w (c:ss) a = w ss (c:a) If you're done then you're done (and dump the accumulator), if it's a space get rid of it (and dump the accumulator), otherwise add it to the acuumulator. That the accumulator is stored backward is a bit wierd, but seems more a consequence of linked lists than recursion per se.
        the5avage 6y ago
        Yeah it's ok ;) Going back to my original comment this code is exactly what I meant with "patterns to deal with other problems". You clearly used a pattern (accumulator) with wich you are familiar. Do you agree that most imperative programmers would not come up with this solution on their own, if you didn't teach them the "accumulator pattern"? For me personally a tutorial with a lot code like that would be interesting. Showing me another version of a recursive descent parser doesn't teach me anything, because I know how to write it (with recursion!!!) in an imperative language...
chriswarbo 6y ago
> While I don't mind the toy problems, all those toy problems have something in common... > They can be easily solved with recursion. As a sibling mentions, recursion is pretty much required in pure functional programming. There is no notion of time or sequencing: everything we write is a definition. If we don't call another function, then our program will finish; if we don't use recursion (either directly, indirectly via functions like `map`, or via a chain of mutually-recursive definitions) then our program's behaviour will be fixed by the structure of our code (e.g. the number of calls we write). That's fine for simple calculations, but most useful programs depend on the structure of their data (e.g. processing lines in a file, etc.); that requires recursion, since we can't hard-code the right number of calls ahead of time.
- flubert 6y ago
  General recursion is equivalent to goto. It is nicer when recursion can be wrapped up in a higher level combinator (map, fold, etc.) or other even higher level abstraction. That's one thing the array languages (APL, J, etc.) got right.
  - chriswarbo 6y ago
    > General recursion is equivalent to goto. Yes, but goto requires a whole bunch of machinery in order to make any sense. It (a) needs a notion of time/sequencing, (b) needs a notion of statement and (c) needs a notion of labelling. (a) and (b) are often taken as given in imperative programming languages (e.g. C, assembly, etc.), but Haskell has none of them. It's hard to ascribe any meaning to "goto" in Haskell; other than some embedded language like ST or something. > It is nicer when recursion can be wrapped up in a higher level combinator (map, fold, etc.) or other even higher level abstraction. I agree, but I was counting those as (indirect) recursion for the purposes of explaining the parent's observation.

chongli 6y ago

Recursion is equivalent to iteration. You can solve any problem you like with it. The problem with those tutorials is that they’re trying to do two things at once: 1) teach you Haskell and 2) advocate for Haskell. I’m currently working as a full time assistant for one of the first year computer science courses at my university. This course is taught in a teaching dialect of Racket which does not allow mutation or side effects of any kind. That doesn’t stop the profs from creating assignments with real world applicability such as graffiti stroke recognizers and decision tree learning algorithms. The key is that they’re not trying to make Racket look good, so the patterns of recursion can get pretty ugly at times.

the5avage 6y ago
> Recursion is equivalent to iteration. You can solve any problem you like with it. Maybe my comment was somehow badly written, because you (and the only other reply from chriswarbo) clearly misunderstood me. I know that recursion is equivalent to iteration^^ My point was that some problems fit the one or the other better. Look at fft for example. The algorithm is easy with recursion but hard with iteration. For other problems its the opposite.
- tasuki 6y ago
  Which problems are hard to solve with recursion instead of iteration?
  - the5avage 6y ago
    I found something like splitting a string into words not very intuitive... Also the classical (recursive) fibonacci function everyone shows has accidental complexity of O(2^n). If you want a sane version it looks definitely more complicated than the iterative version. I never saw a recursive version of bresenham's line plotting algorithm so this might be a good candidate as well ;)
    - chongli 6y ago
      I found something like splitting a string into words not very intuitive... Just use a couple of accumulators (one for the current word, one for the list of completed words). Also the classical (recursive) fibonacci function everyone shows has accidental complexity of O(2^n). That's moving the goalposts. If you want a really fast fibonacci function then the classical iterative algorithm [which is O(n)] is not what you want either. Better to use matrix exponentiation which you can implement nicely with recursion using a divide-and-conquer approach similar to mergesort, giving you fibonacci with time O(log(n)). I never saw a recursive version of bresenham's line plotting algorithm so this might be a good candidate as well ;) There's nothing special about Bresenham's line algorithm that would make it particularly challenging to implement with recursion.
    - a1369209993 6y ago
      > splitting a string into words not very intuitive It seems okay? split :: String -> [String] split s = w s "" where w [] "" = [] w [] a = [reverse a] w (' ':ss) "" = w ss "" w (' ':ss) a = reverse a : w ss "" w (c:ss) a = w ss (c:a) If you're done then you're done (and dump the accumulator), if it's a space get rid of it (and dump the accumulator), otherwise add it to the acuumulator. That the accumulator is stored backward is a bit wierd, but seems more a consequence of linked lists than recursion per se.
      - the5avage 6y ago
        Yeah it's ok ;) Going back to my original comment this code is exactly what I meant with "patterns to deal with other problems". You clearly used a pattern (accumulator) with wich you are familiar. Do you agree that most imperative programmers would not come up with this solution on their own, if you didn't teach them the "accumulator pattern"? For me personally a tutorial with a lot code like that would be interesting. Showing me another version of a recursive descent parser doesn't teach me anything, because I know how to write it (with recursion!!!) in an imperative language...

chriswarbo 6y ago

> While I don't mind the toy problems, all those toy problems have something in common... > They can be easily solved with recursion. As a sibling mentions, recursion is pretty much required in pure functional programming. There is no notion of time or sequencing: everything we write is a definition. If we don't call another function, then our program will finish; if we don't use recursion (either directly, indirectly via functions like `map`, or via a chain of mutually-recursive definitions) then our program's behaviour will be fixed by the structure of our code (e.g. the number of calls we write). That's fine for simple calculations, but most useful programs depend on the structure of their data (e.g. processing lines in a file, etc.); that requires recursion, since we can't hard-code the right number of calls ahead of time.

flubert 6y ago
General recursion is equivalent to goto. It is nicer when recursion can be wrapped up in a higher level combinator (map, fold, etc.) or other even higher level abstraction. That's one thing the array languages (APL, J, etc.) got right.
- chriswarbo 6y ago
  > General recursion is equivalent to goto. Yes, but goto requires a whole bunch of machinery in order to make any sense. It (a) needs a notion of time/sequencing, (b) needs a notion of statement and (c) needs a notion of labelling. (a) and (b) are often taken as given in imperative programming languages (e.g. C, assembly, etc.), but Haskell has none of them. It's hard to ascribe any meaning to "goto" in Haskell; other than some embedded language like ST or something. > It is nicer when recursion can be wrapped up in a higher level combinator (map, fold, etc.) or other even higher level abstraction. I agree, but I was counting those as (indirect) recursion for the purposes of explaining the parent's observation.