Способы получить середину списка в Haskell?

Ответ 1

Две версии

• Используя сопоставление с образцом, tail и init:

  middle :: [a] -> [a]
  middle [email protected](_:_:_:_) = middle $ tail $ init l
  middle l           = l
  

• Использование length, take, signum, mod, drop и div:

  middle :: [a] -> [a]
  middle xs = take (signum ((l + 1) `mod` 2) + 1) $ drop ((l - 1) `div ` 2) xs
    where l = length xs
  

Второй - это в основном однострочный (но для чтения) используется where.

Ответ 2

Я не предъявляю никаких требований к производительности, хотя он обрабатывает только элементы списка один раз (мое предположение заключается в том, что вычисление length t является операцией O (N), поэтому я избегаю этого), но здесь мое решение:

mid [] = []                      -- Base case: the list is empty ==> no midpt
mid t = m t t                    -- The 1st t is the slow ptr, the 2nd is fast
  where m (x:_) [_] = [x]        -- Base case: list tracked by the fast ptr has
                                    -- exactly one item left ==> the first item
                                    -- pointed to by the slow ptr is the midpt.
        m (x:y:_) [_,_] = [x,y]  -- Base case: list tracked by the fast ptr has
                                    -- exactly two items left ==> the first two
                                    -- items pointed to by the slow ptr are the 
                                    -- midpts
        m (_:t) (_:_:u) = m t u  -- Recursive step: advance slow ptr by 1, and
                                    -- advance fast ptr by 2.

Идея состоит в том, чтобы в список было два "указателя", один шаг в каждой точке рекурсии и один, который увеличивается на два.

(что, по существу, предложил Карл Стротрич)

Ответ 3

Просто для вашего удовольствия, решение от кого-то, кто не говорит на Haskell:

Напишите рекурсивную функцию, которая принимает два аргумента: a1 и a2 и передает ваш список в качестве обоих. При каждой рекурсии отбрасывайте 2 из a2 и 1 из a1. Если у вас нет элементов для a2, вы будете в середине a1. Вы можете обработать случай только одного элемента, оставшегося в a2, чтобы ответить, нужны ли вам 1 или 2 элемента для вашего "среднего".

Ответ 4

Я попытался написать функцию, которая возвращает середину списка (2 элемента для четных длин, 1 для нечетных), и я хотел бы услышать, как другие будут реализовывать его в

Правильная структура данных для правильной задачи. В этом случае вы указали что-то, что имеет смысл только в конечном списке, не так ли? Нет никакого "среднего" для бесконечного списка. Итак, просто прочитав описание, мы знаем, что список Haskell по умолчанию не может быть лучшим решением: мы можем платить за ленту даже тогда, когда она нам не нужна. Обратите внимание на то, что из многих решений трудно избежать 2*O(n) или O(n). Единосвязанные ленивые списки не слишком хорошо сочетаются с проблемой квази-массива.

К счастью, у нас есть конечный список в Haskell: он называется Data.Sequence.

Давайте рассмотрим это наиболее очевидным образом: 'index (length/2)'.

Data.Seq.length O(1) соответствует документам. Data.Seq.index O(log(min(i,n-i))) (где я думаю, я = index и n = length). Позвольте просто называть его O(log n). Довольно хорошо!

И обратите внимание, что даже если мы не начинаем с Seq и должны преобразовать [a] в Seq, мы все равно можем победить. Data.Seq.fromList O(n). Поэтому, если наш соперник был решением O(n)+O(n), например xs !! (length xs), такое решение, как

middle x = let x' = Seq.fromList x in Seq.index(Seq.length x' `div` 2)

будет лучше, так как это будет O(1) + O(log n) + O(n), что упрощается до O(log n) + O(n), очевидно, лучше, чем O(n)+O(n).

(я оставляю в качестве упражнения читателю, изменяя середину, чтобы возвращать 2 элемента, если длина четная, а 1 - нечетная. И, без сомнения, можно было бы лучше справиться с массивом с операциями длины и индексирования с постоянным временем, массив не список, я чувствую.)

Ответ 5

Решение Haskell, вдохновленное Carl answer.

middle = m =<< drop 1
   where m []  = take 1
         m [_] = take 2
         m (_:_:ys) = m ys . drop 1

Ответ 6

Если последовательность является связанным списком, обход этого списка является доминирующим фактором эффективности. Поскольку нам нужно знать общую длину, нам нужно пройти по крайней мере один раз. Существует два эквивалентных способа получения средних элементов:

• Поверните список один раз, чтобы получить длину, затем перейдите его половину, чтобы перейти к средним элементам.
• Перемещайте список в двойные шаги и отдельные шаги одновременно, так что, когда первый обход останавливается, второй обход находится посередине.

Оба должны иметь одинаковое количество шагов. Второй, по-моему, излишне сложный.

В Haskell это может быть примерно так:

middle xs = take (2 - r) $ drop ((div l 2) + r - 1) xs
          where l = length xs
                r = rem l 2

Ответ 7

Решение F # на основе ответа Carl:

let halve_list l =
    let rec loop acc1 = function
        | x::xs, [] -> List.rev acc1, x::xs
        | x::xs, [y] -> List.rev (x::acc1), xs
        | x::xs, y::y'::ys -> loop (x::acc1) (xs, ys)
        | [], _ -> [], []
    loop [] (l, l)

Это довольно легко изменить, чтобы получить медианные элементы в списке:

let median l =
    let rec loop acc1 = function
        | x::xs, [] -> [List.head acc1; x]
        | x::xs, [y] -> [x]
        | x::xs, y::y'::ys -> loop (x::acc1) (xs, ys)
        | [], _ -> []
    loop [] (l, l)

Более интуитивный подход использует счетчик:

let halve_list2 l =
    let rec loop acc = function
        | (_, []) -> [], []
        | (0, rest) -> List.rev acc, rest
        | (n, x::xs) -> loop (x::acc) (n - 1, xs)
    let count = (List.length l) / 2
    loop [] (count, l)

И действительно уродливая модификация для получения медианных элементов:

let median2 l =
    let rec loop acc = function
        | (n, [], isEven) -> []
        | (0, rest, isEven) ->
            match rest, isEven with
            | x::xs, true -> [List.head acc; x]
            | x::xs, false -> [x]
            | _, _ -> failwith "Should never happen"
        | (n, x::xs, isEven) -> loop (x::acc) (n - 1, xs, isEven)

    let len = List.length l
    let count = len / 2
    let isEven = if len % 2 = 0 then true else false
    loop [] (count, l, isEven)

Получение длины списка требует прохождения по всему содержанию хотя бы один раз. К счастью, совершенно легко написать собственную структуру данных списка, которая содержит длину списка в каждом node, что позволяет получить длину в O (1).

Ответ 8

middle xs =
  let (ms, len) = go xs 0 [] len
  in  ms

go (x:xs) i acc len =
  let acc_ = case len `divMod` 2 of
         (m, 0) -> if m  == (i+1) then (take 2 (x:xs))
                                  else acc
         (m, 1) -> if m  == i     then [x]
                                  else acc
  in go xs (i+1) acc_ len

go [] i acc _ = (acc,i)

Это решение проходит список только один раз, используя ленивую оценку. Пока он перемещается по списку, он вычисляет длину и затем возвращает ее функции:

let (ms, len) = go xs 0 [] len

Теперь можно вычислить средние элементы:

let acc' = case len `divMod` 2 of
...

Ответ 9

Очень простое, но неэлегантное и не столь тонкое решение может быть:

middle :: [a] -> Maybe [a]
middle xs
    | len <= 2 = Nothing
    | even len = Just $ take 2 . drop (half - 1) $ xs
    | odd len = Just $ take 1 . drop (half) $ xs
    where 
          len = length xs
          half = len `div` 2

Ответ 10

Это повторяется дважды над списком.

mid xs = m where
  l = length xs
  m | l `elem` [0..2] = xs
  m | odd l = drop (l `div` 2) $ take 1 $ xs
  m | otherwise = drop (l `div` 2 - 1) $ take 2 $ xs

Ответ 11

Я живу для одного лайнера, хотя этот пример работает только для нечетных списков. Я просто хочу растянуть мой мозг! Спасибо за удовольствие =)

foo d = map (\(Just a) -> a) $ filter (/=Nothing) $ zipWith (\a b -> if a == b then Just a else Nothing) (Data.List.nub d) (Data.List.nub $ reverse d)

Ответ 12

Я не очень разбираюсь в себе, но я попробовал это.

Сначала тесты (да, вы можете делать TDD с помощью Haskell)

module Main
where
import Test.HUnit
import Middle
main = do runTestTT tests
tests = TestList [ test1
                 , test2
                 , test3
                 , test4
                 , test_final1
                 , test_final2
                 ]

test1         =     [0]    ~=? middle [0]
test2         =     [0, 1] ~=? middle [0, 1]
test3         =     [1]    ~=? middle [0, 1, 2]
test4         =     [1, 2] ~=? middle [0, 1, 2, 3]
test_final1   =     [3]    ~=? middle [0, 1, 2, 3, 4, 5, 6]
test_final2   =     [3, 4] ~=? middle [0, 1, 2, 3, 4, 5, 6, 7]

И решение, к которому я пришел:

module Middle
where

middle a = midlen a (length a)

midlen (a:xs) 1 = [a]
midlen (a:b:xs) 2 = [a, b]
midlen (a:xs) lg = midlen xs (lg - (2)) 

Он будет пересекать список дважды, один раз, чтобы получить длину и половину больше, чтобы получить середину, но мне все равно O (n) (и получение середины чего-то означает, чтобы получить длину, поэтому нет причин чтобы избежать этого).

Ответ 13

Мое решение, мне нравится держать вещи простыми:

middle [] = []
middle xs | odd (length xs) = [xs !! ((length xs) `div` 2)]
          | otherwise = [(xs !! ((length xs) `div` 2)),(reverse $ xs) !! ((length xs)`div` 2)]

Использование !! в Data.List как функция для получения значения по заданному индексу, который в этом случае составляет половину длины списка.

Изменить: он действительно работает сейчас

Ответ 14

Вот моя версия. Это был просто быстрый подъем. Я уверен, что это не очень хорошо.

middleList [email protected](_:_:_:_) = take (if odd n then 1 else 2) $ drop en xs
    where n = length xs
          en = if n < 5 then 1 else 2 * (n `div` 4)
middleList xs = xs

Я пробовал.:)

Если кто-то чувствует, что комментирует и говорит мне, насколько ужасно или хорошо это решение, я был бы очень признателен. Я не очень хорошо разбираюсь в Haskell.

EDIT: улучшено с предложениями kmc на # haskell-blah

EDIT 2: теперь можно принимать входные списки длиной менее 5.

Ответ 15

Мне нравится ответ Сванте. Моя версия:

> middle :: [a] -> [a]
> middle [] = []
> middle xs = take (r+1) . drop d $ xs
>  where
>    (d,r) = (length xs - 1) `divMod` 2

Ответ 16

Другое однострочное решение:

--
middle = ap (take . (1 +) . signum . (`mod` 2) . (1 +) . length) $ drop =<< (`div` 2) . subtract 1 . length
--

Ответ 17

Странно, что эта совершенно очевидная формулировка еще не появилась:

middle []    = []
middle [x]   = [x]
middle [x,y] = [x,y]
middle xs    = middle $ init $ tail xs

или

middle [email protected](_ : _ : _ : _) = middle $ init $ tail xs
middle xs                 = xs

Однострочник:

middle xs = case xs of { (_ : _ : _ : _) -> middle $ init $ tail xs; _ -> xs; }