1

具有极简变化的工作版本，感谢@Matt、Petr 和 Landei ！！！

insert :: (Ord el) => el -> Menge el -> Menge el
insert a (Menge (x:xs)) = ins a (Menge (x:xs)) (Menge [])

ins a (Menge []) (Menge ys) = Menge (ys ++ [a])
ins a (Menge xs@(x:xs')) (Menge ys)
       | a <  x     = Menge (ys ++ [a] ++ xs)
       | a >  x     = ins a (Menge xs') (Menge (ys ++ [x]))
       | otherwise  = Menge (ys ++ xs)

有一个自己的数据类型 Menge，就像一个列表，我应该在正确的位置插入一个元素......

module Menge (
  Menge,
  empty,
  insert,
  ins
) where

data Menge el = Menge [el] deriving (Eq)

instance (Show el) => Show (Menge el) where
 show (Menge liste) = "{" ++ (elms liste) ++ "}"
     where
       elms :: (Show a) => [a] -> String
       elms [] = ""
       elms (x:[]) = show x
       elms (x:xs) = show x ++ ", " ++ elms xs

empty :: Menge el
empty = Menge []

insert :: (Ord el) => el -> Menge el -> Menge el
--insert a (Menge []) = (Menge [a]) 
insert a (Menge (x:xs)) = ins a (Menge (x:xs)) (Menge [])

ins a (Menge []) (Menge (y:ys)) = (Menge ((y:ys) ++ [a]))
ins a (Menge (x:xs)) (Menge (y:ys)) 
       | a <  x = (Menge ((y:ys) ++ [a] ++ (x:xs)))
       | a >  x = ins a (Menge xs) (Menge ((y:ys) ++ [x]))
       | a >  x && xs == [] = error "same function as: ins a empty (Menge (y:ys))"
       | a == x = (Menge ((y:ys) ++ (x:xs)))
       | otherwise = error "blabla"

我输入：insert 2 (Menge ([1,3]))，在我看来，我应该像这样工作：

--> ins 2 (Menge (1:3)) empty --> 2 > 1 --> ins 2 (Menge [3]) (Menge [] ++ [1])
--> ins 2 (Menge [3]) (Menge [1]) --> 2 < 3 --> (Menge ([1] ++ [2] ++ [3])) --> [1,2,3]

但相反，我得到：“函数 ins 中的非详尽模式”

如果我输入相同的错误：ins 2 (Menge ([1,3])) (Menge [])，所以第一步工作。似乎编译器不喜欢“empty”/“(Menge [])”，因为如果我输入: ins 2 (Menge ([1,3])) (Menge [1,3])，我会得到{1, 3, 2}答案。

4

3 回答 3

3

我看到两个主要问题ins：

  1. 看来您正在尝试使用empty- 的值进行模式匹配，这是行不通的。Any Menge，包括具有非空列表的列表，都将匹配，因为empty这里用作函数的本地绑定（隐藏您的其他绑定）。所以你需要：

    ins a (Menge []) (Menge (y:ys)) = ...

    这个问题的一个症状是我的haskell安装pattern match(es) are overlapped在我加载你的代码时给了我一个警告。这基本上意味着你有一些死代码。

  2. 当第三个参数是时，您的模式不匹配Menge []- 我认为这是给出您显示的消息的错误（尽管我不确定，因为您没有给出整个错误消息）。你的两个方程只匹配非空列表。

    例如：

    ghci> ins x (Menge []) (Menge [])

    不会匹配任何模式。

于 2012-08-13T17:50:56.750 回答
1

我试图insert从头开始实施。首先，我添加了函数以使解构unmenge值更容易，并且还将您的Menge声明修改为新类型（只是性能优化 - 这样，它实际上不会在运行时创建新的数据构造函数）。

newtype Menge el = Menge { unmenge :: [el] }
  deriving (Eq)

现在，insert函数可以写成如下：

insert :: (Ord el) => el -> Menge el -> Menge el
insert a (Menge []) = (Menge [a]) 
insert a (Menge xs@(x:xs'))
    | a <= x    = Menge (a : xs)
    | otherwise = Menge (x : unmenge (insert a (Menge xs')))

如果a小于列表中的第一项，则只是在前面添加。如果不是，则它是x最小的数，因此将其放在第一位，然后a递归地插入到其余数中。

请注意，此解决方案不是尾递归的。

更简单的解决方案是使用span函数：

insert :: (Ord el) => el -> Menge el -> Menge el
insert a (Menge xs) = let (smaller, bigger) = span (<= a) xs
                        in Menge (smaller ++ [a] ++ bigger)

编辑：您更正的代码似乎按预期工作。我把它简化了一点，但我没有改变任何实质性的东西：

insert :: (Ord el) => el -> Menge el -> Menge el
insert a (Menge (x:xs)) = ins a (Menge (x:xs)) (Menge [])

ins a (Menge []) (Menge ys) = Menge (ys ++ [a])
ins a (Menge xs@(x:xs')) (Menge ys)
       | a <  x     = Menge (ys ++ [a] ++ xs)
       | a >  x     = ins a (Menge xs') (Menge (ys ++ [x]))
       | otherwise  = Menge (ys ++ xs)

一些改进的想法：

  • 看看as-patterns（我在这里使用过它们）。

  • 在列表末尾添加一个元素具有O(n)复杂性 - 必须重新计算整个列表。最好以相反的顺序保持列表并仅在最后修复它：

    ins a (Menge []) (Menge ys) = Menge (reverse ys ++ [a])
ins a (Menge xs@(x:xs')) (Menge ys)
       | a <  x     = Menge (reverse (a : ys) ++ xs)
       | a >  x     = ins a (Menge xs') (Menge (x : ys))
       | otherwise  = Menge (reverse ys ++ xs)

  • 有一个称为Data.Set的数据结构可以满足您的需要：使用二叉树保存已排序的元素集。大多数操作具有O(1)或O(log n)复杂度。

于 2012-08-13T18:06:21.717 回答
1

我的看法：

insert :: (Ord el) => el -> Menge el -> Menge el
insert a mx = merge (Menge [a]) mx 

merge :: (Ord el) => Menge el -> Menge el -> Menge el
merge mx (Menge []) = mx  
merge (Menge []) my = my
merge (Menge (x:xs)) (Menge (y:ys)) 
  | x == y = merge (Menge xs) (Menge (y:ys))   
  | x < y = merge (Menge xs) (Menge (x:y:ys))
  | x > y = let Menge zs = merge (Menge (x:xs)) (Menge ys) 
            in Menge (y:zs)
于 2012-08-14T07:45:32.057 回答