All Questions
14 questions
1
vote
2
answers
109
views
Implementing a factorial function in Scala
I'm working out of Scala for the Impatient (3rd Edition). (I'm not doing this for a class.). I'm trying to implement a factorial function using to and reduceLeft without a loop or recursion. This ...
- 1,177
1
vote
1
answer
172
views
Elm - fold on recursive type with list does not compile
I'm following this article on catamorphism and I'm trying to define a fold function for a recursive data type like this
type Node anyType
= Leaf Id (Maybe anyType)
| Tree Id (List (Node ...
- 1,274
0
votes
4
answers
1k
views
How to structure an accumulator for fold_left with index access
I want to write a function that takes a List [a_n; a_n-1; ...; a_0] with an accumulator acc.
The function is supposed to calculate the sum of every element in the whole list raised to the i'th power. ...
- 37
11
votes
1
answer
405
views
What is the connection between primitive recursion and catamorphisms?
Using the following catamorphism for natural numbers I can implement various arithmetic algorithms whithout having to deal with recursion:
cataNat :: b -> (b -> b) -> Natural -> b
cataNat ...
user5536315
0
votes
1
answer
232
views
Is the Y Combinator a left fold or a right fold?
The Y combinator (from the wikipedia article) is defined as:
Y = \f.(\x.f(x x)) (\x.f(x x))
so when we call Y on g:
Y g = (\f.(\x.f(x x)) (\x.f(x x))) g
= (\x.g(x x)) (\x.g(x x))
= g((\x.g(x x)) ...
- 2,694
3
votes
2
answers
190
views
How to fold data structures from non-tail recursive algorithms?
I have a variadic lifting function that allows for flat monadic chains without deeply nested function composition:
const varArgs = f => {
const go = args =>
Object.defineProperties(
...
user5536315
1
vote
4
answers
3k
views
Implement Foldl function in Javascript
I'm trying to write a function that implements foldl in JavaScript. I'm trying to use recursion in the function but not being able to implement it.
var foldl = function(f, acc, array) {
if (...
- 1,862
2
votes
1
answer
1k
views
Primitive Recursive function
In A tutorial on universality and expressiveness of fold chapter 4.1, it states that this pattern of recursion
h y [] = f y
h y (x:xs) = g y x xs (h y xs)
is primitive recursion, but I don't ...
- 85
6
votes
2
answers
4k
views
Explanation of lists:fold function
I learning more and more about Erlang language and have recently faced some problem. I read about foldl(Fun, Acc0, List) -> Acc1 function. I used learnyousomeerlang.com tutorial and there was an ...
- 1,047
2
votes
3
answers
602
views
How can operations like map, filter and reverse can be defined in terms of a reduce?
In this blog entry, "CSP and transducers in JavaScript", the author states:
First, we have to realise that many array (or other collection) operations like map, filter and reverse can be defined in ...
- 36k
3
votes
3
answers
903
views
How can this function be written using foldr?
I have this simple function which returns a list of pairs with the adjacents elements of a list.
adjacents :: [a] -> [(a,a)]
adjacents (x:y:xs) = [(x,y)] ++ adjacents (y:xs)
adjacents (x:xs) = []
...
- 1,144
48
votes
4
answers
11k
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, ((...
- 1,066
4
votes
2
answers
10k
views
reversing a list in OCaml using fold_left/right
UPDATE - Solution
Thanks to jacobm for his help, I came up with a solution.
// Folding Recursion
let reverse_list_3 theList =
List.fold_left (fun element recursive_call -> recursive_call::...
- 46.8k
177
votes
7
answers
50k
views
Implications of foldr vs. foldl (or foldl')
Firstly, Real World Haskell, which I am reading, says to never use foldl and instead use foldl'. So I trust it.
But I'm hazy on when to use foldr vs. foldl'. Though I can see the structure of how ...
- 17.1k