Haskell: манипулирование списком

Question

Я хочу написать функцию, которая принимает список ввода и управляет им следующим образом:

Шаг 1: Возьмите первый элемент списка и последний элемент списка и соедините его вподсписок

Шаг 2: Возьмите второй элемент списка и второй последний элемент списка и соедините его в следующем подсписке.

Шаг 3: Возьмите третий элемент списка итретий последний элемент списка и объединить его в следующем подсписке.

Продолжить в соответствии с той же схемой (для списка из n элементов) ...

Если количество элементовиз списка ввода нечетный элемент n / 2 из списка ввода будет добавлен как последний подсписок списка вывода.

Пример:

[1,2,3,4,5,6,7]

-- should be transformed to

[[1,7],[2,6],[3,5],[4]]

Я уже написал функцию, которая принимаеткаждые 2 элемента списка и объединяет его в подсписки, и мне интересно, может ли этот код помочь мне с моей проблемой выше:

g2 :: [a] -> [[a]]
g2 [] = []
g2 (x1:x2:xs) = [x1,x2]: g2 xs
g2 xs = [xs]

Answer 1

Вот тот, который делает это за один проход:

pairs :: [a] -> [[a]]
pairs xs = fst (go xs xs) where
  go (x:xs) (_:_:ys) = f x (go xs ys)
  go (x:xs) [_]      = ([[x]],xs)
  go xs     []       = ([],xs)

  f x (xs,y:ys) = ([x,y]:xs,ys)

Как это работает?Давайте рассмотрим первые два аргумента go first и, в частности, эту строку:

  go (x:xs) (_:_:ys) = f x (go xs ys)

Оба эти аргумента находятся в одном и том же списке (xs), но мы берем 2 элемента из одного,и только один от другого.Зачем?Итак, мы знаем, когда мы достигли середины.Посмотрите на эту функцию для сравнения:

halfway xs = go xs xs
  where
    go (_:xs) (_:_:ys) = go xs ys
    go xs _ = xs

>>> halfway [1..6]
[4,5,6]

Теперь, как только мы дойдем до середины, нам нужно будет "сжать" ее с другим списком.Но это должно быть наоборот!как нам это сделать?Удобный способ перевернуть любую функцию за один проход - сначала написать ее в виде сгиба.Вот zip, записанный в виде сгиба:

zip = foldr (\x k (y:ys) -> (x,y) : k ys) (const [])

Чтобы «перевернуть» его, вы просто применяете его как foldl, а не как foldr (вы также должны перевернуть крышку).

Для нашего использования мы в основном строим базу по ходу (в форме k).Так что ни одна наша функция не выглядит так:

pairs :: [a] -> [[a]]
pairs xs = go xs xs (const []) where
  go (y:ys) (_:_:zs) k = go ys zs (f y k)
  go (y:ys) [_]      k = [y] : k ys
  go ys     []       k = k ys

  f x k (y:ys) = [x,y] : k ys -- same `f` as from `zip`

Есть еще одна проблема: список возвращается в неправильном порядке.Чтобы исправить это, мы заменим список на список различий и поменяем порядок добавлений.

Наконец, мы снимаем CPS с функции и получаем выше.

Answer 2

Вот пример использования transpose

import Data.List

g2 xs =
  transpose [take (x + y) xs, take x (reverse xs)]
    where (x, y) = (length xs) `divMod` 2

Answer 3

Обратите внимание, что мы должны использовать drop 1 вместо tail, чтобы избежать ошибок для списков нечетной длины.

g2 :: [a] -> [[a]]
g2 [] = []
g2 xs = [first xs] ++ (g2 . drop 1 $ init xs)
    where first (x:[]) = [x]
          first xs = [head xs, last xs]

Answer 4

Еще два, второй использует unfoldr :

pair xs = take (length xs `div` 2) $ zip xs (reverse xs)
-- Note: uses tuples instead of lists

import Data.List
pairs2 = unfoldr (\xs ->
    if length xs < 2 
    then Nothing
    else Just ([head xs, last xs], init.tail $ xs))

xs = [2,3,4,7,6]
pair xs   -- [(2,6),(3,7)]
pair2 xs  -- [[2,6],[3,7]]