正如 @WillemVanOnsem 所建议的,您可能想尝试编写一个将目标元素向右移动一格的函数。即使这个简化的问题也可能非常具有挑战性!
看看是否可以实现直接递归版本。它的结构可能与您的类似delete
函数,除非它会swap两个元素,而不是在关键点删除一个元素。 (答案在底部——寻找定义simpleShiftRight
.)
完成此操作后,请尝试使用这种替代方法,该方法的优点是更容易推广到解决您的原始问题。
首先,使用delete
不是很有帮助,因为delete
“忘记”元素原来在哪里。例如,以下两者:
delete '.' "abc.def"
delete '.' "abcde.f"
yield "abcdef"
,并且尚不清楚如何使用此结果,例如将句点位置向右移动一个位置。
相反,您真正想做的是将字符串分成目标元素之前和之后的部分。也就是说,你想定义一个函数split
其工作原理如下:
> split '.' "abc.def"
("abc","def")
> split '.' "abcde.f"
("abcde","f")
有了这个结果,改变周期就变得容易多了。
例如,如果我们想将周期向右移动一位,我们可以首先定义一个函数
pairRight :: ([a], [a]) -> ([a], [a])
其工作原理如下:
> pairRight ("abc","def")
("abcd","ef")
> pairRight ("abcde","f")
("abcdef","")
和一个函数
rejoin :: a -> ([a], [a]) -> [a]
其工作原理如下:
> rejoin '.' ("abcd","ef")
"abcd.ef"
> rejoin '.' ("abcdef","")
"abcdef."
并将它们组合起来:
> rejoin '.' (pairRight (split '.' "abc.def"))
"abcd.ef"
> rejoin '.' (pairRight (split '.' "abcde.f"))
"abcdef."
得到一个将字符向右移动一位的函数。
Now, split
可以根据库函数来定义break
,像这样:
split :: Eq a => a -> [a] -> ([a], [a])
split x xs = let (a, _:b) = break (==x) xs in (a,b)
能实现一下功能吗pairRight
and rejoin
?它们不应该太难,但如果你遇到困难,答案就在底部。
您可能还想尝试定义split
从头开始而不使用break
。这是一个有点棘手的递归函数。如果您从“明显”的方法开始:
split :: Eq a => a -> [a] -> ([a], [a])
split x (y:ys) | x == y = (..., ys)
| otherwise = split x ys
split _ [] = error "split: target not found"
你会遇到问题。不清楚如何填写...
因为你在递归中丢弃了列表的开头。希望您已经了解到解决此问题的一种方法是引入一个额外的参数来跟踪已处理的列表元素并定义一个函数:
split' :: Eq a => a -> [a] -> [a] -> ([a], [a])
split' x ls (r:rs) = ...
where x
是我们要寻找的元素,ls
是我们已经处理过的列表左侧的元素集(其中我们没有找到x
), and (r:rs)
是我们仍在处理的列表的右侧。
如果您需要进一步的提示,这里有一个模板:
split' x ls (r:rs) | x == r = (..., ...)
| otherwise = split' x (...) rs
split' _ _ [] = error "split: target not found"
可以填写一下吗...
这里?如果可以的话,您可以定义:
split :: Eq a => a -> [a] -> ([a], [a])
split x xs = split' x [] xs
一旦你有split
, pairRight
, and rejoin
定义后,您应该能够将它们组合成一个函数:
shiftRight :: Eq a => a -> [a] -> [a]
可以将目标元素向右移动一位。
如果你遇到困难,这里有一个完整的定义shiftRight
和它的
帮手:
shiftRight :: (Eq a) => a -> [a] -> [a]
shiftRight x xs = rejoin x (pairRight (split x xs))
-- alternative definition of split:
-- split :: Eq a => a -> [a] -> ([a], [a])
-- split x xs = let (a, _:b) = break (==x) xs in (a,b)
split :: Eq a => a -> [a] -> ([a], [a])
split x xs = split' x [] xs
split' :: Eq a => a -> [a] -> [a] -> ([a], [a])
split' x ls (r:rs) | x == r = (ls, rs)
| otherwise = split' x (ls ++ [r]) rs
split' _ _ [] = error "split: target not found"
pairRight :: ([a], [a]) -> ([a], [a])
pairRight (ls, r:rs) = (ls ++ [r], rs)
rejoin :: a -> ([a], [a]) -> [a]
rejoin x (ls, rs) = ls ++ [x] ++ rs
在这个版本中,尝试shiftRight
不在列表中或已经位于最右边位置的目标将给出错误。您可能想尝试解决这个问题。 (注意split
可以返回一个Maybe [a]
,产生Nothing
如果没有找到目标;修改起来也不应该太困难pairRight
因此,如果该对已经尽可能向右移动,则它不会执行任何操作。)
如果这对于一个简单的问题来说似乎很麻烦,我想确实如此。在实际代码中,经验丰富的 Haskell 程序员可能会编写直接递归版本:
simpleShiftRight :: (Eq a) => a -> [a] -> [a]
simpleShiftRight x (y:z:rest) | x == y = z:y:rest
| otherwise = y : simpleShiftRight x (z:rest)
simpleShiftRight _ rest = rest
或者这个使用break
:
simpleShiftRight :: (Eq a) => a -> [a] -> [a]
simpleShiftRight x xs = case break (==x) xs of
(ls, y:z:rs) -> ls ++ z:y:rs
_ -> xs
两个版本都很简洁,处理所有极端情况,并且“显然是正确的”。正如前面提到的,缺点是这个版本不太容易推广到您的原始问题。
上面的版本确实很容易概括——你只需要替换pairRight
具有更复杂的配对移位功能。例如,定义:
pairRightN :: Int -> ([a],[a]) -> ([a],[a])
pairRightN n (ls, r:rs) | n > 0 = pairRightN (n-1) (ls ++ [r], rs)
pairRightN _ (ls, rs) = (ls, rs)
允许您处理所有正值n
(即,无论有多大,都可以)。进一步将其推广到处理左移也不是太难。