Tagged Questions
216
votes
16answers
53k views
What is tail-recursion?
Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean?
48
votes
8answers
6k views
Implications of foldr vs. foldl (or foldl')
Firstly, Real World Haskell, which I am reading, says to never use foldl instead of foldl'. So I trust it.
But I'm hazy on when to use foldr vs. foldl'. Though I can see the structure of how they ...
47
votes
2answers
2k views
Recursion schemes for dummies?
I'm looking for some really simple, easy-to-grasp explanations of recursion schemes and corecursion schemes (catamorphisms, anamorphisms, hylomorphisms etc.) which do not require following lots of ...
46
votes
1answer
1k views
What are paramorphisms?
Reading through this classic paper, I'm stuck on paramorphisms. Unfortunately the section is quite thin, and the Wikipedia page doesn't say anything.
My Haskell translation is:
para :: (a -> [a] ...
34
votes
8answers
2k views
Functional Programming - Lots of emphasis on recursion, why?
I am getting introduced to Functional Programming [FP] (using Scala). One thing that is coming out from my initial learnings is that FPs rely heavily on recursion. And also it seems like, in pure FPs ...
14
votes
1answer
349 views
Why is the non-deterministic choice function in Curry's std lib not defined straightforwardly but rather with a helper 2-argument function?
Consider a function choose in Curry programming language with the specification that "(choose xs) non-deterministically chooses one element from the list xs".
I'd implement it straighforwardly ...
13
votes
4answers
1k views
Why is foldl defined in a strange way in Racket?
In Haskell, like in many other functional languages, the function foldl is defined such that, for example, foldl (-) 0 [1,2,3,4] = -10.
This is OK, because foldl (-) 0 [1, 2,3,4] is, by definition, ...
12
votes
5answers
2k views
Are there problems that cannot be written using tail recursion?
Tail recursion is an important performance optimisation stragegy in functional languages because it allows recursive calls to consume constant stack (rather than O(n)).
Are there any problems that ...
11
votes
2answers
5k views
tail recursion vs. forward recursion
Can someone give me the difference between these two kinds recursions and example?
specifically in ocaml. Thanks
11
votes
7answers
1k views
What's a good way to rewrite this non-tail-recursive function?
For some reason, I am having trouble thinking of a good way to rewrite this function so it uses constant stack space. Most online discussions of tree recursion cheat by using the Fibonacci function ...
11
votes
1answer
597 views
Why does ocaml need both “let” and “let rec”? [duplicate]
Possible Duplicate:
Why are functions in Ocaml/F# not recursive by default?
OCaml uses let to define a new function, or let rec to define a function that is recursive. Why does it need both ...
10
votes
6answers
1k views
In C# is it a good practice to use recursive functions in algorithms?
In many functional languages using a recursion is considered to be a good practice. I think it is good because of the way compiler optimizes functional language's code.
But is it a good practice to ...
10
votes
5answers
6k views
Towers of Hanoi with K pegs
The Towers of Hanoi problem is a classic problem for recursion. You are given 3 pegs with disks on one of them, and you must move all the disks from one peg to another, by following the given rules. ...
9
votes
5answers
448 views
Best way to accumulate results in a vector in Clojure? (Pure functional code seems ugly and verbose)
...Maybe imperative programming with mutable data is just drilled too deep into my brain, but I find the code for building up vectors of data in Clojure to be verbose, unwieldy, and convoluted. There ...
9
votes
4answers
278 views
Haskell recursion and memory usage
I'm quite new to Haskell, and I'm getting comfortable with the idea of replacing loops with recursion. I'm fiddling around with a pet project, and I wanted to test some text input functionality so I ...
