Snippets tagged recursion
-
Filtering lists
Two functions showing how to filter functional lists using the specified predicate. First version uses naive recursion and the second one is tail-recursive using the accumulator parameter.
76 people like this
Like the snippet!Posted: 13 years ago by Tomas Petricek
-
Random walk
Create sequence of floating point values generated by random walk process. Functional solution using sequence expressions and yield! construct in a tail-call position.
39 people like this
Like the snippet!Posted: 13 years ago by Tomas Petricek
-
Continuation-Passing Mnemonics
Continuations provide a means whereby heap space can be traded for stack depth (heap space being generally more plentiful than stack depth). They are especially useful where tail recursion is not possible. Here are a couple of simple continuation examples that can be extended to cover more complex scenarios.
100 people like this
Like the snippet!Posted: 13 years ago by Neil Carrier
-
Function to generate all possible combinations where combination "ab" != "ba"
Function to generate all possible combinations where combination "ab" is different then "ba"
6 people like this
Like the snippet!Posted: 13 years ago by Ankur Dhama
-
Split a list
Three ways to split a list in half (but not necessarily in the middle). A forth version added that's very short and should be fast, as we only use List.fold. New champ found.
83 people like this
Like the snippet!Posted: 13 years ago by Dmitri Pavlenkov
-
Combinatorial functions
Here is my F# take on some combinatorial functions from the book "Introduction to Functional Programming" by Richard Bird and Philip Wadler.
5 people like this
Like the snippet!Posted: 13 years ago by Cesar Mendoza
-
Euler #5
Euler #5 solution
4 people like this
Like the snippet!Posted: 13 years ago by Michael Falanga
-
Y(n) Polyvariadic fixpoint
Encoding mutually-recursive functions with a Polyvariadic fixpoint combinator.
5 people like this
Like the snippet!Posted: 12 years ago by Nick Palladinos
-
recursive to dynamic programming with ycombinator
Dynamic programming is equivalent to recursion + some way to remember the results (as far as I undertand) The y combinator allows to "tie" a previously "untied" recursion, which itself allows to compositionally inject additional steps in the recursion. This allows to go from recursion to dynamic programming in a structured way. This exemple is a bit contrived, as there are no overlapping subproblems, which would be the case in more interesting problem (dtw etc..)
3 people like this
Like the snippet!Posted: 11 years ago by Nicolas2
-
Generating a tree from a generic type
I needed a function to generate a tree from a c# class that had some odd semantics, but when I refactored it, I realised almost everyone must have something similar knocking around their codebase, so here's mine.
0 people like this
Like the snippet!Posted: 11 years ago by Sean Newham
-
Palindrom
Check string of palindroms
2 people like this
Like the snippet!Posted: 10 years ago by Zhukoff Dima
-
Retry loop, no tricks
Less-nonsense 8-line retry function that will retry a function a specified up to `maxRetries` times while it throws. After the retries, any remaining exception is allowed to propagate. Accepts a before function to allow you to wait/report when a retry is taking place
2 people like this
Like the snippet!Posted: 10 years ago by Ruben Bartelink
-
Transitive Reduction of a graph
Implements a simple algorithm to compute the transitive reduction of a graph. The transitive reduction of a graph is the minimal set of edges with the same transitive closure
0 people like this
Like the snippet!Posted: 8 years ago by Jose Iborra
-
Recursor
A sugar around IEnumerator<'a> to make it nicer to use with recursive functions
5 people like this
Like the snippet!Posted: 6 years ago by manofstick
-
Step-by-step explanation of the Y combinator
Describes a function called "fix" that can be used to generate recursive functions from non-recursive functions, with some simple examples. (Updated with slightly improved comments.)
9 people like this
Like the snippet!Posted: 5 years ago by Brian Berns
-
Use of Active Patterns to convert integer to Roman numerals
A good use case for demonstrating the use of active patterns
6 people like this
Like the snippet!Posted: 4 years ago by Faisal Waris
-
Rotate or shift lists
This rotates or shifts a list. Unlike http://www.fssnip.net/qY/title/Rotate-List, which runs exponentially, this runs at O(n). In case of overflow (i.e., shift index is larger than the size of the list) will run at most once more with the modulo. This is done to prevent using `List.length` prior to entering the function, as that would lead to a perf punishment of an extra O(n) on each invocation. For large lists, `shift largeList 1` would then get a big performance hit.
1 people like this
Like the snippet!Posted: 2 years ago by Abel Braaksma
-
Projecting lists
Three functions showing how to implement projection for functional lists. First version uses naive recursion and the second one is tail-recursive using the accumulator parameter. The third version extends this with continuation passing.
73 people like this
Like the snippet!Posted: 13 years ago by Tomas Petricek
-
Recursive functions
Show's how to define a recursive function that will calculate a fibonacci number.
16 people like this
Like the snippet!Posted: 13 years ago by Robert Pickering
-
Memoization and Tail Recursive Function
Hi, I expressed Memoization and Memoization Tail Recursive on the functions. I hope something useful.
22 people like this
Like the snippet!Posted: 13 years ago by zecl
-
Project Euler #182
The RSA encryption is based on the following procedure: Generate two distinct primes p and q. Compute n=pq and phi=(p-1)(q-1). Find an integer e, 1
Like the snippet!Posted: 13 years ago by Natallie Baikevich
-
IRC Jokes
Simple snippet that demonstrates recursively defined discriminated unions, the Y combinator (for encoding recursive functions) and recursive processing of tree-like structures
6 people like this
Like the snippet!Posted: 13 years ago by Daniel Jackson
-
Abstraction of the "tail-recursive loop" pattern
A novel, due to performance inadequacy, abstraction of the "tail-recursive loop" pattern. Approaching what a built-in language feature might look like.
3 people like this
Like the snippet!Posted: 13 years ago by Stephen Swensen
-
Random Subset
A function that takes a random subset from a seq<'T>.
1 people like this
Like the snippet!Posted: 12 years ago by Taha Hachana
-
FizzBuzz with Rule Engine
Inspired by http://dave.fayr.am/posts/2012-10-4-finding-fizzbuzz.html Rules are in a list of lambdas that can be easily modified. A pattern-matching recursive function applies them in the correct order.
7 people like this
Like the snippet!Posted: 12 years ago by Richard Broida
-
Combinator for tail-recursive functions
The snippet defines a combinator 'tailrec' that can be used to express tail-recursive functions. If you use 'tailrec' and do not mark your function as recursive, then the function will be a tail-recursive one.
1 people like this
Like the snippet!Posted: 11 years ago by Tomas Petricek
-
Rabbits and Recurrence Relations
One solution to Rosalind rabbits problem.
2 people like this
Like the snippet!Posted: 10 years ago by Michel Caradec
-
Negamax Tic-Tac-Toe
Plays the perfect game of Tic-Tac-Toe using the Negamax algorithm.
2 people like this
Like the snippet!Posted: 10 years ago by Richard Dalton
-
Accumulate a value by applying a function - in two different styles
Two different approaches to the problem of starting with a value, applying a function to it n times, and accumulating a result.
0 people like this
Like the snippet!Posted: 8 years ago by Kit Eason
-
Factorial using Int64, Double and BigInteger
Recursive Factorial using Int64, Double and BigInteger with execution time.
0 people like this
Like the snippet!Posted: 7 years ago by Carlos Quintanilla
-
Seemingly impossible program defines equality between arbitrary functions
It is well known that it is impossible to define equality between arbitrary functions. However, there is a large class of functions for which we can determine equality, and it’s strange and surprising. We explore this idea using F# code translated from the Swift programming language.
3 people like this
Like the snippet!Posted: 5 years ago by Brian Berns
-
Counting Languages - Converting integers to ASTs and back again
This little snippet shows you how you can create a simple recursive data type and define a pair of functions that maps the set of positive integers to unique instances in the AST and back again.
2 people like this
Like the snippet!Posted: 5 years ago by Steve Goguen
-
List2D module
Contains operations for working with 2-dimensional lists.
3 people like this
Like the snippet!Posted: 3 years ago by Pavel Tatarintsev