It’s pretty well-known that general function equality is undecidable in general, so you’ll have to pick a subset of the problem that you’re interested in. You might consider some of these partial solutions: Presburger arithmetic is a decidable fragment of first-order logic + arithmetic. The universe package offers function equality tests for total functions with … Read more
This library is a straightforward combinatorization of the well-known technique of memoization. Let’s start with the canonical example: fib = (map fib’ [0..] !!) where fib’ 0 = 0 fib’ 1 = 1 fib’ n = fib (n-1) + fib (n-2) I interpret what you said to mean that you know how and why this … Read more
One way to think of this is that a value of type IO a is a “recipe”, containing a list of instructions that if performed would have side effects. Constructing that “recipe” though, does not have any side effects. So a haskell program (whose type is IO ()) is basically a computation that constructs such … Read more
Let me use a shorter example than the posted one: original :: Int -> Int original n | n < 10 && n > 7 = 1 — matches 8,9 | n < 12 && n > 5 = 2 — matches 6,7,10,11 | n < 12 && n > 3 = 3 — matches … Read more
Nope. But you can write this: data Foo = X { name :: String, age :: Int } | A { name :: String } | B { name :: String } | C { name :: String } | D { name :: String } and then have name :: Foo -> String. You … Read more
I think you can do this in general with ScopedTypeVariables which GHC supports. This certainly compiles: {-# LANGUAGE ScopedTypeVariables #-} foo :: forall a. (a -> a) -> a -> a foo f arg = bar arg where bar :: a -> a bar a = f a Note the “forall a.”
Understanding higher-order functions Haskell, as a functional language, supports higher-order functions (HOFs). In mathematics HOFs are called functionals, but you don’t need any mathematics to understand them. In usual imperative programming, like in Java, functions can accept values, like integers and strings, do something with them, and return back a value of some other type. … Read more
Well, one way to look at it is that Haskell translates the return type polymorphism that you’re thinking of into parametric polymorphism, using something called the dictionary-passing translation for type classes. (Though this is not the only way to implement type classes or reason about them; it’s just the most popular.) Basically, fromInteger has this … Read more
Consider the GADT data S a where S :: Show a => S a and the execution of the code foo :: S a -> a -> String foo s x = case s of S -> show x In a dictionary-based Haskell implementation, one would expect that the value s is carrying a class … Read more
What you got here is the value polymorphism restriction of ML language family. The aim of the restriction is to settle down let-polymorphism and side effects together. For example, in the following definition: let r = ref None r cannot have a polymorphic type ‘a option ref. Otherwise: let () = r := Some 1; … Read more