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).
Added
Cleaned up and with changes based on the answer, the code below appears to be working:
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 :: (Integral 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"
Then I see
*Main> floyd tester 2
(1,3)
and given this test function (essentially like the one from the Wikipedia example), this makes sense. If you start a x0 = 2 then the sequence is 2 -> 6 -> 1 -> 3 -> 6..., so mu is 1 (you have to move in one element to hit the start of the sequence) and lam is 3 (the sequence repeats every three entries).
I suppose there's some question about whether to always consider the first point as burn-in before you can possibly "repeat".
If anyone has advice on this, I'd be grateful. In particular, my cntr construct seems un-functional to me.. it's a way of counting how many repeated calls are made. I'm not sure if there's a better/different way that's less like saving the state of a variable.
You can't say Integer a or Int a. You probably mean Integral a. Integral encompasses all types that are integers of some kind, including Integer and Int.
The thing before => is not a type but a type class. SomeTypeClass a => a means "any type a that is a member of the type class SomeTypeClass".
You can do this:
function :: Int -> String
which is a function that takes an Int and returns a String. You can also do this:
function :: Integer -> String
which is a function that takes an Integer and returns a String. You can also do this:
function :: Integral i => i -> String
which is a function that takes either an Int, or an Integer, or any other integer-like type and returns a String.
About your second question, your guess is right. You coud do
mu :: (Eq a, Integral b) => (a -> a) -> a -> a -> b -> (b, a)
Your commented questions:
You could do something like
function :: (Show a, Integral a) => a -> String
That will restrict a to be any type that is both a member of Show and Integral.
Then you just write out the other arguments as specific types. You could do
function :: (Integral a) -> a -> Int -> String
which takes any integer-like type a, and then an Int and returns a String.