理解Haskell声明中的多个类型/类型类

Question

我正在尝试学习Haskell与学习你一个Haskell ...但我不耐烦,并希望实现我最喜欢的算法,看看我能不能.

我正在研究用于循环检测的乌龟/野兔算法(Floyd算法).

这是我到目前为止的代码:

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

这试图将逻辑分解为三个步骤.首先得到f_idx == f_ {2*idx}的索引,然后从开始移动得到参数mu(从第一个元素到循环开始的距离),然后移动直到你重复一次(循环的长度) .

这个功能floyd是我把这些放在一起的hacky尝试.

除了这有点不起作用,我也有加载模块的问题,我不知道为什么:

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.

更改所有出现Integer于Int或Num不让它更好.

我不理解误用Int.在本教程中,函数的大多数类型声明始终具有表单

function_name :: (Some_Type a) => <stuff involving a and possibly other types>

但是,当我替换(Eq a)使用(Num a)或(Int a)我得到一个类似的错误(类型应用于太多的参数).

我试过读这个,但它不同意教程的符号(例如几乎所有这些例子中定义的函数).

我必须严重误解类型与类型类,但是这正是我想我也明白,带给我做类型声明,如上面我的代码.

后续可能是:函数类型声明中有多个TypeClasses的语法是什么？就像是:

mu :: (Eq a, Int b) => (a -> a) -> a -> a -> b -> (b, a)

(但这也给出了编译错误,说Int应用于太多的参数).

添加

清理并根据答案进行更改,以下代码似乎正在运行:

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" 

然后我明白了

*Main> floyd tester 2
(1,3)

并且给出了这个测试函数(基本上类似于维基百科示例中的函数),这是有道理的.如果你开始a x0 = 2然后序列是2 -> 6 -> 1 -> 3 -> 6...,那么mu是1(你必须在一个元素中移动以命中序列的开头)并且lam是3(序列每三个条目重复一次).

我想有一些问题是,在你可以"重复"之前是否总是将第一点视为老化.

如果有人对此提出建议,我将不胜感激.特别是,我的cntr构造对我来说似乎没有用.它是一种计算重复调用次数的方法.我不确定是否有更好/不同的方式,更不像保存变量的状态.

Answer 1

你不能说Integer a或Int a.你可能意味着Integral a.Integral包含所有类型的整数类型,包括Integer和Int.

之前的东西=>不是类型而是类型类.SomeTypeClass a => a表示" a类型类成员的任何类型SomeTypeClass".

你可以这样做:

function :: Int -> String

这是一个接受Int并返回a 的函数String.你也可以这样做:

function :: Integer -> String

这是一个接受Integer并返回a 的函数String.你也可以这样做:

function :: Integral i => i -> String

这是一个函数,它接受一个Int或一个Integer或任何其他类似整数的类型并返回一个String.

关于你的第二个问题,你的猜测是正确的.你做得好

mu :: (Eq a, Integral b) => (a -> a) -> a -> a -> b -> (b, a)

您的评论问题:

1.如果你想确保某个类型是多个TypeClasses的成员,你会怎么做？

你可以做点什么

function :: (Show a, Integral a) => a -> String

这将限制a到是任何类型的包括大量部件Show和Integral.

2.假设您只想将Type限制为驻留在某些参数的TypeClass中,并且您希望其他参数属于特定类型？

然后你只需将其他参数写成特定类型.你可以做到

function :: (Integral a) -> a -> Int -> String

它采用任何类似整数的类型a,然后一个Int并返回一个String.