Tagged Questions
261
votes
16answers
66k views
What is tail-recursion?
Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean?
54
votes
8answers
7k 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 ...
52
votes
3answers
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 ...
47
votes
1answer
2k 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] ...
37
votes
8answers
3k 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 ...
16
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 ...
14
votes
1answer
365 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
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
12
votes
5answers
8k 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. ...
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
943 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
5answers
723 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 ...
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
2answers
266 views
I couldn't understand the Y-Combinator, so I tried to implement it and ended up with something shorter, which worked. How is that possible?
I couldn't understand the Y-combinator, so I tried to implement a function that enabled recursion without native implementation. After some thinking, I ended up with this:
Y = λx.(λv.(x x) v)
Which ...
