Как получить середину списка в Хаскеле?

Question

Я только начал изучать функциональное программирование, используя Haskel.

Я медленно читаю Лекции Эрика Мейера на 9-м канале (я уже посмотрел первые 4) и в 4-м видео Эрик объясняет, как работает tail, и это меня очаровало.

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

• Наименьшее количество кода Haskell
• Самый быстрый код на Haskell

Если бы вы могли объяснить свой выбор, я был бы очень признателен.

Мой код для начинающих выглядит так:

middle as | length as > 2   = middle (drop 2 (reverse as))
          | otherwise       = as

Answer 1

Я не претендую на производительность, хотя он только один раз обрабатывает элементы списка (я предполагаю, что вычисления 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.

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

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

Answer 2

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

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

Answer 3

Две версии

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

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

2. Использование 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).

Answer 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))) (где я думаю, что i = индекс, а n = длина). Давайте просто назовем это 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, если длина нечетная. И, без сомнения, можно было бы добиться большего успеха с массивом с постоянной длиной и операциями индексации, но Я считаю, что массив - это не список.

Answer 5

Решение Haskell, вдохновленное Ответом Карла .

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

Answer 6

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

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

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

В Хаскеле это может выглядеть примерно так:

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

Answer 7

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

Answer 8

F # решение, основанное на ответе Карла:

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)

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

Answer 9

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

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

Answer 10

Я сам не очень хакеллер, но я попробовал это.

Сначала тесты (да, вы можете сделать 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) (а получение середины чего-либо подразумевает получение его длины, поэтому нет причин чтобы избежать этого).