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

Для метки времени Unix:

:r! date +\%s

можно также отобразить эту команду на ключ (например, F12) в VIM при использовании его много:

Помещенный это в Ваш .vimrc:


map  <F12> :r! date +\%s<cr>
16
задан Josh Lee 16 November 2009 в 01:35
поделиться

15 ответов

Две версии

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

     middle :: [a] -> [a]
    средний l @ (_: _: _: _) = средний $ хвост $ init l
    средний l = l
    
  2. Используя length , возьмите , signum , mod , drop и div ]:

     средний :: [a] -> [a]
    средний xs = take (signum ((l + 1) `mod` 2) + 1) $ drop ((l - 1)` div `2) xs
     где l = длина xs
    

Второй - однострочный (но для удобства чтения использует , где ).

15
ответ дан 30 November 2019 в 15:11
поделиться

Вот моя версия. Это был просто быстрый пробег. Уверен, не очень.

middleList xs@(_:_:_:_) = 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.

РЕДАКТИРОВАТЬ: Улучшено с учетом предложений от kmc на # haskell-blah

РЕДАКТИРОВАТЬ 2: Теперь могу принимать списки ввода длиной менее 5.

0
ответ дан 30 November 2019 в 15:11
поделиться

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

> middle :: [a] -> [a]
> middle [] = []
> middle xs = take (r+1) . drop d $ xs
>  where
>    (d,r) = (length xs - 1) `divMod` 2
0
ответ дан 30 November 2019 в 15:11
поделиться

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

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

0
ответ дан 30 November 2019 в 15: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)
0
ответ дан 30 November 2019 в 15:11
поделиться

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

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
0
ответ дан 30 November 2019 в 15:11
поделиться

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

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
0
ответ дан 30 November 2019 в 15:11
поделиться

Решение 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).

1
ответ дан 30 November 2019 в 15:11
поделиться
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
...
1
ответ дан 30 November 2019 в 15:11
поделиться

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

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

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

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

middle xs = take (2 - r) $ drop ((div l 2) + r - 1) xs
          where l = length xs
                r = rem l 2
2
ответ дан 30 November 2019 в 15:11
поделиться

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

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.

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

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

17
ответ дан 30 November 2019 в 15:11
поделиться

Просто для вашего развлечения, решение от того, кто не говорит на Haskell:

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

16
ответ дан 30 November 2019 в 15:11
поделиться

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

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

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

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

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

И обратите внимание, что даже если мы не начнем с Seq и должны преобразовать [a] в Seq , мы все еще можем победить. Data.Seq.fromList - это O (n) . Итак, если бы нашим соперником было решение O (n) + O (n) , такое как xs !! (длина 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) .

11
ответ дан 30 November 2019 в 15:11
поделиться

Мое решение, я предпочитаю упрощать:

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 в качестве функции для получения значения при заданном index, который в данном случае составляет половину длины списка.

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

0
ответ дан 30 November 2019 в 15:11
поделиться

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

middle = m =<< drop 1
   where m []  = take 1
         m [_] = take 2
         m (_:_:ys) = m ys . drop 1
5
ответ дан 30 November 2019 в 15:11
поделиться
Другие вопросы по тегам:

Похожие вопросы: