简单功能，可移动列表的特定元素 [英] simple function that shifts specific element of a list

问题描述

我是Haskell的新手，我试图弄清楚如何创建函数:

I am new to Haskell and I am trying to figure out how to make a function:

    shift:: Eq a => a -> [a] -> Int -> [a]
    shift x (h:t) z

输入:通用列表和相同类型的元素x

Input: a generic list and an element x of the same type

前提条件:元素x存在于列表中

Precondition: element x exists in the list

输出:

如果n< 0，将x左移n，直到到达列表的第一位

if n < 0, shift x left by n until reach the first of the list

如果n> 0，则将x右移n，直到到达列表的最后一个

if n > 0, shift x right by n until reach the last of the list

如果n == 0，则从列表中删除x(总是谈论x的首次出现，它在列表中可能显示超过1次).

if n == 0, remove x from the list (always talking about the first appearance of x, it could be shown more than 1 time in the list).

请记住我已完成删除功能

Keep in mind that i have completed my delete function

    delete :: Eq b => b -> [b] -> [b]

查找所需元素的第一个外观并将其删除.我猜我可以在班次内使用删除.任何帮助都将受到赞赏.

that finds the first appearance of the desired element and deletes it. I could use delete inside shift i guess. Any kind of help is appreciated.

[一些I/O样本]

     Main> shift 3 [] 5
     []
     Main> shift 0 [1,2,3,4] 4
     [1,2,3,4]
     Main> shift 3 [1,2,3,4,3,2,1] 3
     [1,2,4,3,2,3,1]
     Main> shift 6 [1,2,3,4,5,6,7,8] 7
     [1,2,3,4,5,7,8,6]
     Main> shift 'k' "skin" 0
     "sin"
     Main> shift '.' "factor.bit." (-2)
     "fact.orbit."
     Main> shift '.' "0000.1111.00" (-10)
     ".00001111.00"
     Main> shift "one" ["one", "two", "three"] (-2)
     ["one","two","three"]
     Main> shift "one" ["one", "two", "three"] 1
     ["two","one","three"]
     Main> shift "three" ["one", "two", "three"] 5
     ["one","two","three"]

推荐答案

如@WillemVanOnsem所建议，您可能想尝试编写将目标元素向右移动一个空格的函数.甚至这个简化的问题也很有挑战性！

As @WillemVanOnsem suggests, you may want to try writing a function that shifts a target element one space to the right. Even this simplified problem might very well be challenging!

查看是否可以实现直接递归版本.它的结构可能与您的delete函数类似，不同之处在于它将交换两个元素，而不是在关键点放置一个元素. (底部的答案-查找simpleShiftRight的定义.)

See if you can implement a direct recursive version. It could be similar in structure to your delete function, except it will swap two elements instead of dropping an element at the critical point. (Answer at the bottom -- look for the definition of simpleShiftRight.)

完成此操作后，请尝试使用这种替代方法，该方法的优点是可以更轻松地推广到解决您的原始问题.

Once you've done that, try working through this alternative approach which has the advantage that it will more easily generalize to solving your original problem.

首先，使用delete并不是很有帮助，因为delete会忘记"元素最初所在的位置.例如，以下两项:

First, using delete isn't very helpful, because delete "forgets" where the element originally was. For example, both of the following:

delete '.' "abc.def"
delete '.' "abcde.f"

收益率"abcdef"，目前尚不清楚如何使用此结果来将周期移动到其所在位置的右侧.

yield "abcdef", and it's not clear how to use this result to, say, shift the period one position to the right of where it was.

相反，您真正想做的是将字符串分成目标元素之前和之后的部分.也就是说，您想定义一个函数split，其功能如下:

Instead, what you'd really like to do is break a string up into the parts before and after the target element. That is, you'd like to define a function split that works like this:

> split '.' "abc.def"
("abc","def")
> split '.' "abcde.f"
("abcde","f")

有了这个结果，改变周期变得更加容易.

With this result, shifting the period becomes much easier.

例如，如果我们想将周期右移一个位置，我们可以先定义一个函数

For example, if we wanted to shift the period one position to the right, we could start by defining a function

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."

获得将字符向右移动一个空格的功能.

to get a function that shifts a character one space to the right.

现在，可以使用库函数break来定义split，如下所示:

Now, split can be defined in terms of the library function break, like so:

split :: Eq a => a -> [a] -> ([a], [a])
split x xs = let (a, _:b) = break (==x) xs in (a,b)

可以实现功能pairRight和rejoin吗?他们不应该太辛苦，但是如果您陷入困境，答案就在底部.

Can you implement the functions pairRight and rejoin? They shouldn't be too hard, but if you get stuck the answer's at the bottom.

您可能还想尝试从头开始定义split，而不使用break.这是一个有点棘手的递归函数.如果您从显而易见"的方法开始:

You might also want to try defining split from scratch without using break. It's a slightly tricky recursive function. If you start with an "obvious" approach:

split :: Eq a => a -> [a] -> ([a], [a])
split x (y:ys) | x == y    = (..., ys)
               | otherwise = split x ys
split _ [] = error "split: target not found"

您会遇到问题.目前尚不清楚如何填写...，因为您已经在递归中丢掉了列表的开头.希望您已经了解到，解决此问题的一种方法是引入一个额外的参数来跟踪已处理的列表元素并定义一个函数:

you'll run into a problem. It's not clear how to fill in the ... because you've sort of thrown away the start of the list in the recursion. Hopefully you've already learned that one way around this is to introduce an extra parameter to keep track of the list elements already processed and define a function:

split' :: Eq a => a -> [a] -> [a] -> ([a], [a])
split' x ls (r:rs) = ...

其中x是我们要查找的元素，ls是我们已经处理过的列表左侧的元素集(在其中找不到x的副本) )，而(r:rs)是我们仍在处理的列表的右侧.

where x is the element we're looking for, ls is the set of elements on the left side of the list that we've already processed (where we didn't find a copy of x), and (r:rs) is the right side of the list that we're still processing.

如果您需要进一步的提示，请使用以下模板:

If you need a further hint, here's a template:

split' x ls (r:rs) | x == r    = (..., ...)
                   | otherwise = split' x (...) rs
split' _ _ [] = error "split: target not found"

您可以在此处填写...吗?如果可以，则可以定义:

Can you fill in the ... here? If you can, then you can define:

split :: Eq a => a -> [a] -> ([a], [a])
split x xs = split' x [] xs

一旦定义了split，pairRight和rejoin，您应该可以将它们组合为一个函数:

Once you have split, pairRight, and rejoin defined, you should be able to combine them into a function:

shiftRight :: Eq a => a -> [a] -> [a]

可以将目标元素向右移动一个位置.

that can shift a target element one position to the right.

如果您遇到困难，这里是shiftRight及其定义的完整定义 帮手:

If you get stuck, here's a complete definition of shiftRight and its helpers:

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也不应该太困难，以使如果该对已经右移则它不会执行任何操作尽其所能.)

In this version, trying to shiftRight a target that isn't in the list or that is already in the rightmost position will give an error. You might want to try fixing that. (Note that split could return a Maybe [a], yielding Nothing if the target isn't found; it also shouldn't be too tough to modify pairRight so that it does nothing if the pair is already shifted right as far as it can go.)

如果这似乎使一个简单的问题困扰很多，我想是的.在实际代码中，经验丰富的Haskell程序员可能会编写直接的递归版本:

If this seems like a lot of bother for a simple problem, I guess it is. In real code, an experienced Haskell programmer would probably write a direct recursive version:

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

两个版本都简洁，可以处理所有极端情况，并且显然是正确的".如前所述，不利之处在于，这个版本很难一概而论地解决您的原始问题.

Both versions are succinct, handle all the corner cases, and are "obviously correct". The downside, as previously mentioned, is that this version isn't quite as easy to generalize to your original problem.

上面的版本确实很容易泛化-您只需用更复杂的成对移位功能替换pairRight.例如，定义:

The version above does generalize pretty easily -- you just need to replace pairRight with a more sophisticated pair shifting function. For example, defining:

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的所有正值(即，无论大小如何，都可以右移).进一步推广它来处理左移也不太困难.

allows you to handle all positive values for n (i.e., all right shifts, no matter how big). It's not too hard to further generalize it to handle left shifts, too.

这篇关于简单功能，可移动列表的特定元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！