Understanding multiple types/typeclasses in Haskell declarations
I'm trying to learn Haskell with Learn You A Haskell... but I got
impatient and wanted to implement a favorite algorithm of mine to see if I
could.
I'm working on the tortoise/hare algorithm (Floyd's algorithm) for cycle
detection.
Here's the code I have so far:
idx :: (Eq a) => (a -> a) -> a -> a -> a
idx f tortoise hare
| (f tortoise) == (f (f hare)) = (f f hare)
| otherwise = (idx f) (f tortoise) (f f hare)
mu :: (Eq a) => (a -> a) -> a -> a -> Integer -> (Integer, a)
mu f tortoise hare cntr
| (f tortoise) == (f hare) = (cntr+1, f tortoise)
| otherwise = (mu f) (f tortoise) (f hare) (cntr+1)
lam :: (Eq a) => (a -> a) -> a -> a -> Integer -> Integer
lam f tortoise hare cntr
| tortoise == hare = cntr+1
| otherwise = (lam f) tortoise (f hare) (cntr+1)
floyd :: (Eq a) => (a -> a) -> a -> (Integer, Integer)
floyd f x0 =
let z = (idx f) x0 x0
(y1, t) = (mu f) x0 z 0
y2 = (lam f) t (f t) 0
in (y1, y2)
tester :: (Integer a) => a -> a
tester a
| a == 0 = 2
| a == 2 = 6
| a == 6 = 1
| a == 1 = 3
| a == 3 = 6
| a == 4 = 0
| a == 5 = 1
| otherwise = error "Input must be between 0 and 6"
(floyd tester) 0
This tries to break the logic up into three steps. First get the index
where f_idx == f_{2*idx}, then move from the start to get the parameter mu
(distance from first element to start of the cycle), then move until you
hit a repeat (length of the cycle).
The function floyd is my hacky attempt to put these together.
Aside from this being somewhat un-functional, I am also having issues
loading the module and I'm not sure why:
Prelude> :load M:\papers\programming\floyds.hs
[1 of 1] Compiling Main ( M:\papers\programming\floyds.hs,
interpreted )
M:\papers\programming\floyds.hs:23:12:
`Integer' is applied to too many type arguments
In the type signature for `tester': tester :: Integer a => a -> a
Failed, modules loaded: none.
Changing all occurrences of Integer to Int or Num don't make it any better.
I'm not understanding the mis-application of Int. Following along in the
tutorial, most type declarations for functions always have the form
function_name :: (Some_Type a) => <stuff involving a and possibly other
types>
But when I replace the (Eq a) with (Num a) or (Int a) I get a similar
error (type applied to too many arguments).
I tried reading this, but it disagrees with the tutorial's notation (e.g.
almost every function defined in these examples).
I must be badly misunderstanding Types vs. TypeClasses, but that's
precisely what I thought I did understand to lead me to make the type
declarations as in my code above.
A follow up might be: what is the syntax for have multiple TypeClasses in
the function type declaration? Something like:
mu :: (Eq a, Int b) => (a -> a) -> a -> a -> b -> (b, a)
(but this also gave compile errors saying Int was applied to too many
arguments).
No comments:
Post a Comment