2

我是 Haskell 的新手。我正在尝试编写一个函数，给定列表l 、列表中存在的元素x以及要插入y的元素：在列表 l 中第一次出现元素 x 之前插入元素 y。如果列表中不存在元素 x ，则保持列表不变。

我在这个问题上遇到了很多麻烦，如果有任何建议，我将不胜感激。

这是我尝试过的（'n' 是元素 x 的第一次出现）：

insertSpecial :: Eq a => a -> a -> [a] -> [a]
insertSpecial let (ys,zs) = splitAt n xs in ys ++ [y] ++ zs
4

5 回答 5

6

怎么样

insertSpecial :: Eq a => a -> a -> [a] -> [a]
insertSpecial x y []              = []
insertSpecial x y (a:as) | a == x = y:a:as
insertSpecial x y (a:as)          = a : insertSpecial x y as

这种方法使用一种称为递归的通用方法。这意味着手头的任务被分解为一个或几个基本案例，其结果可以很容易地定义，而一般案例可以通过将工作分解为多个部分来解决。在一般情况下，然后在较小的任务上递归调用该函数。目标是最终以基本情况结束，此时工作已完成。另请参阅Learn you a Haskell中的这一部分。

因为insertSpecial我们可以定义两个基本情况：

  1. 如果列表为空，则它不包含我们要查找的元素，并且我们希望在这种情况下保持列表不变，因此我们只需返回一个空列表。我们完成了。

  2. 如果列表不为空并且第一个元素是我们要查找的元素，我们将保留y在该列表的前面并返回它。我们又完成了。

这给我们留下了列表不为空但第一个元素不是我们要查找的元素的情况。在这种情况下，我们将工作（列表）分成两部分：第一个元素和其余元素。insertSpecial我们将第一个元素放在通过调用列表的其余部分返回的列表的前面。这就是递归发生的地方：insertSpecial调用本身。

关于这一点可能有点难以理解的一件事是，最后一种情况如何通过在正确的位置插入一个元素来生成一个与原始列表不同的列表。让我们考虑一个例子。假设我们有清单

['h','e','l','o']

请注意，在 Haskell 中，常规字符串只是字符列表，所以['h','e','l','o'] == "helo". 另请注意，这['h','e','l','o']实际上是'h':'e':'l':'o':[]. (:接受一个元素和一个列表并将该元素添加到列表中。它也称为cons )。

'l'现在让我们在前面插入缺失的内容'o'：

 insertSpecial 'o' 'l' "helo"

由于"helo"is not empty'h'被绑定到a并且"elo"被绑定到as（此外，'o'被绑定到x并且'l'被绑定到'y'）。由于a == 'h' /= 'o' == x我们是第三种情况，所以

  insertSpecial 'o' 'l' ('h':"elo") = 'h' : insertSpecial 'o' 'l' "elo"

现在insertSpecial 'o' 'l' "elo"我们再次陷入第三种情况（"elo"不是空的和'o' /= 'e'）：

 insertSpecial 'o' 'l' ('e':"lo") = 'e' : insertSpecial 'o' 'l' "lo"

这又导致了第三种情况：

 insertSpecial 'o' 'l' ('l':"o") = 'l' : insertSpecial 'o' 'l' "o"

现在在最后一个调用中，我们实际上绑定'o'了a等于，x然后我们进入第二种情况，在这种情况下，我们将 () 的值y添加'l'到a( 'o') 和as( [])，所以我们得到：

insertSpecial 'o' 'l' ('o':[]) | 'o' == 'o' = 'l' : 'o' : []

将所有这些替换放在一起，我们得到：

insertSpecial 'o' 'l' "helo" = 
'h' : insertSpecial 'o' 'l' "elo" =
'h' : 'e' : insertSpecial 'o' 'l' "lo" = 
'h' : 'e' : 'l' : insertSpecial 'o' 'l' "o" =
'h' : 'e' : 'l' : 'l' : 'o' : []

并且如上所述'h' : 'e' : 'l' : 'l' : 'o' : [] == ['h','e','l','l','o'] == "hello"。耶。

于 2013-02-08T14:04:43.257 回答
4

您可以在满足条件的第一个位置进行拆分，而不是在索引处拆分，

insertSpecial y x xs = front ++ [y] ++ back
  where
    (front, back) = break (== x) xs

如果你想要一个错误以防你的假设x是列表的一个元素不满足，

insertSpecial y x xs = case break (== x) xs of
                         (front, back@(_:_)) -> front ++ [y] ++ back
                         _ -> error "Didn't find element"

但是直接递归也是一个很好的解决方案。

于 2013-02-08T14:10:10.493 回答
1 
insertSpecial::[Int]->Int->Int->[Int]
insertSpecial [] _ _ = []
insertSpecial list a b = concat [if x == a then [b] ++ [x] else [x] | x<-list]

inserts b before a

于 2013-02-11T00:00:53.960 回答
1

有三种情况

insertSpecial :: Eq a => a -> a -> [a] -> [a]
insertSpecial _ _ []                 = ?
insertSpecial x y (a:as) | a == x    = ?
                         | otherwise = a : rest
  where rest = ?

每一个会发生什么？

第一种情况是您肯定知道该元素不在列表中，因为列表为空。然后返回相同的空列表。

下一种情况是列表的第一个元素是您要查找的元素。然后你只需要返回同一个列表，前面加上 y 。

最后一个递归 case ( otherwise) 是第一个元素不是您要查找的元素，但它可能仍在列表的其余部分中。然后你需要添加到a列表的其余部分，其中列表的其余部分as在y第一次出现之前添加x。

于 2013-02-08T14:06:43.867 回答
1

就折叠而言的一般预测beforeEvery发生

beforeEvery pred y  =  foldr (\ x xs -> if pred x then y : x : xs else x : xs) []

显式展开的递归函数在第一次出现后终止

before :: (a -> Bool) -> a -> [a] -> [a]
before _    _ []                   = []
before pred y (x : xs) | pred x    = y : x : before pred y xs
                       | otherwise = x : before pred y xs

这样

beforeElem x y  =  before (== x) y

或者

beforeElem :: Eq a => a -> a -> [a] -> [a]
beforeElem x y  =  before (== x) y

意义

beforeElem 3 89 [1,2,3,4,5,3,4,5]  ==  [1,2,89,3,4,5,3,4,5]
于 2017-02-17T21:16:18.190 回答