All Questions
44 questions
30
votes
1
answer
746
views
Have "Brodal search trees" really been implemented for practical use?
Brodal et al. demonstrated in their ESA '06 paper the existence of a purely functional structure with logarithmic-time search, update and insertion, and constant-time merge. (Note I'm not talking ...
- 587
0
votes
1
answer
523
views
Testing if one list is a sublist of another without testing equality between elements
I am wondering if one can write a functional program (as in Haskell or OCaml) that takes two lists and determines if the first is a sublist of the second, with the property that the program cannot ...
- 143
7
votes
1
answer
2k
views
Hindley Milner type inference for mutually recursive functions
I'm making a strongly typed toy functional programming language. It uses the Hindley Milner algorithm as type inference algorithm.
Implementing the algorithm, I have a question on how to infer types ...
- 1,035
5
votes
4
answers
1k
views
Functional way to split a map of lists into a list of maps
I'm a bit stuck on this problem. I feel like I'm "thinking backwards" and it's confusing me a bit.
I have a Map[Long, Seq[String]] which I would like to convert into a Seq[Map[Long, String]]. Going ...
- 53
6
votes
2
answers
626
views
Proper way of applying two (or many) option values to a function in F#
Recently I discovered a style of programming which is very useful (and pretty) in functional world called Railway oriented programming.
For example when want to create a pipeline of functions that ...
- 1,128
18
votes
1
answer
1k
views
OCaml functors, Haskell type classes, and multiple derivation
It is well-known that OCaml has a parametric polymorphism and this leads to some limitations. Haskell, through its type classes, offers an ad hoc polymorphism, which is, obviously, very convenient in ...
- 429
3
votes
0
answers
215
views
What is the F# answer to Haskell's typeclasses and OCaml's functors? [duplicate]
It is important to be able to associate a type with a bundle of functions that know how to operate on that type and know its specifics. Modules in F# are intrinsically static, they can be loaded but ...
- 19.8k
8
votes
2
answers
492
views
Can we have type variables in constructor position in the Hindley Milner type system?
In Haskell we can write the following data type:
data Fix f = Fix { unFix :: f (Fix f) }
The type variable f has the kind * -> * (i.e. it is an unknown type constructor). Hence, Fix has the kind (*...
- 74.3k
6
votes
4
answers
621
views
Is there a name for ADT with explicit subtyping?
I'm looking for a proper name for a data type that combines ADT with explicit subtyping.
In one of my applications, I use a structure similar to ADT to represent parse trees, on which I perform ...
- 1,926
6
votes
4
answers
482
views
Is there a standard higher order function for applying a transformation several times?
I'm thinking of a function like this:
> let applyN (initial : 't) (n:int) (f : 't -> 't) = seq {1..n} |> Seq.fold (fun s _ -> f s) initial;;
val applyN : initial:'t -> n:int -> f:('...
- 2,126
26
votes
4
answers
7k
views
Functional Breadth First Search
Functional depth first search is lovely in directed acyclic graphs.
In graphs with cycles however, how do we avoid infinite recursion? In a procedural language I would mark nodes as I hit them, but ...
- 4,956
29
votes
2
answers
920
views
Is it possible to get the infinite kind error in Haskell 98?
I am implementing a kind system for a new functional programming language and I am currently writing the function to unify two kinds. There are four cases two consider:
+---------+---------+----------...
- 74.3k
43
votes
6
answers
5k
views
What's the reason of 'let rec' for impure functional language OCaml?
In the book Real World OCaml, the authors put why OCaml uses let rec for defining recursive functions.
OCaml distinguishes between nonrecursive definitions (using let) and recursive definitions (...
- 192k
3
votes
2
answers
2k
views
How to iterate over all elements in a record type with the same type (purely functional iterators for record types)
Is there a good way to iterate, fold, or loop over all elements in a record that have the same type? For example, in the following OCaml code
type foo = {
a : int;
b : float;
c : int;
...
- 6,360
1
vote
1
answer
213
views
Convert this algorithm into a procedure, that doesn't use recursion
Few weeks ago I had a task to accomplish and my way of thinking is correct, but the implementation I gave at that time was horrible. I have a chance to get some points but only if I provide a correct ...
- 123