Haskell: Know if the type of a variable derives Eq

user_13751795 0
Viewed 111

I'm new to Haskell and i have the following problem. I have the function foo that has to apply a function (given by parameter) until there are no more changes. That's the signature of the function 

foo :: (a-> a )-> a-> a

I tried this

foo f x = if ((f x) == x) then x else foo (f (f x))

I get this 

No instance for (Eq a) arising from a use of `=='

I know why i get it (a is generic so the compiler doesn't know if derives Eq) but don't know how to solve. I was thinking a way to divide the function in two cases (when the input derives Eq and when it doesn't) but I didn't find a way to do it. All the solutions that i found to this problem changed the signature of the function to Eq a but i am not allowed to change the signature.

PS: I don't care what does the function when the parameter doesn't derive Eq because i wont use it in this case.

Edit: I did the corrections that willen said

haskell
1 Answers

There aren't a lot of functions with that type. Ignoring things that just produce errors or infinite loops, you have

foo :: (a -> a) -> a -> a
foo f _ = r where r = f r

Idiomatically, we'd write this using Data.Function.fix:

fix :: (a -> a) -> a
fix f = r where r = f r

foo f _ = fix f

This just gives you f (f (f (f ...))) which may or may not be well-defined, depending on what f turns out to be.

bar :: Natural -> (a -> a) -> a -> a
bar 0 _ a = a
bar n f a = f (bar (n - 1) f a)

Applying bar to a natural number produces a function of the type you desire applying the argument function the given number of times.

That's it. There are no more.

{foo} ∪ {bar n | n ∈ N}

is the entire set of interesting (partial) functions of the type you've given. If you want more interesting functions, you need more constraints.

How does foo relate to bar? Well, one way to think about foo is as what you'd get by applying bar to "infinity". We could define the extended natural numbers (the Alexandroff one-point compactification of the natural numbers) like this:

data ExtendedNat = N Natural | Inf

but that really doesn't help explain foo and bar. A much more natural approach is to use lazy natural numbers instead:

data Nat = Z | S Nat

Now infinity is represented as S (S (S ...)):

infty :: Nat
infty = fix S

We can write

barf :: Nat -> (a -> a) -> a -> a
barf Z _ a = a
barf (S n) f a = f (bar n f a)

Now foof is specifically

foof = barf infty
user_14776670
Related