如何在哈斯克尔的名单中占据中间位置?

两个版本

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 为了可读性)。

虽然它只处理列表中的元素一次(我的假设是计算 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.

其思想是在列表中有两个“指针”,一个在递归的每个点上增加一个步骤,另一个增加两个步骤。

(这基本上就是卡尔·斯莫特里茨建议的)

只是为了你的娱乐,一个不说哈斯克尔语的人的解决方案:

编写一个接收两个参数(A1和A2)的递归函数,并将列表作为两个参数传入。在每次递归中,从a2中删除2,从a1中删除1。如果你没有A2元素,你将处于A1元素的中间。您可以处理A2中只剩下1个元素的情况,以回答您的“中间”是否需要1或2个元素。

我试着写一个函数,它返回一个列表的中间部分(2个项目表示偶数,1个表示奇数),我想听听其他人是如何实现它的。

正确问题的正确数据结构。在这种情况下,您已经指定了一些仅在 有限的 名单,对吧?无限列表中没有“中间”项。因此,只要阅读描述,我们就知道默认的haskell列表可能不是最好的解决方案:即使我们不需要它,我们也可能为懒惰付出代价。注意有多少解决方案难以避免 2*O(n) 或 O(n) . 单链接的惰性列表与准数组问题不太匹配。

幸运的是,我们在Haskell中确实有一个有限的列表:它被称为 Data.Sequence .

让我们用最明显的方法来解决这个问题:“索引(长度/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项。毫无疑问,使用具有恒定时间长度和索引操作的数组可以做得更好,但我觉得数组不是一个列表。)

Haskell解决方案灵感来自 Carl's answer .

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

如果序列是链表,则该链表的遍历是效率的主要因素。因为我们需要知道整个长度,所以我们必须至少遍历列表一次。有两种等效的方法来获取中间元素:

• 遍历列表一次以获取长度,然后将其遍历一半以获取中间元素。
• 以两步和一步同时遍历列表,以便第一次遍历停止时,第二次遍历位于中间。

两者都需要相同数量的步骤。在我看来,第二个问题是不必要的复杂。

在哈斯克尔,可能是这样的:

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

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

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)

获取列表的长度要求至少遍历其整个内容一次。幸运的是,编写自己的列表数据结构是非常容易的,它在每个节点中保存列表的长度,允许您以o(1)获取长度。

奇怪的是,这个非常明显的公式还没有出现:

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

一个非常直截了当,却又缺乏法律依据,而且不那么简单的解决方案可能是:

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

这将在列表上迭代两次。

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

虽然这个例子只适用于奇数列表,但我只为一行程序而活。我只是想舒展一下我的大脑!谢谢你的乐趣=)

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)

我自己不是哈斯凯勒,但我试过这个。

首先测试(是的,可以使用haskell进行TDD)

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)(获取中间部分意味着获取长度,所以没有理由避免它)。

我的解决方案,我喜欢保持简单:

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中,作为函数获取给定索引的值,在本例中,该索引是列表长度的一半。

编辑:它现在实际工作了

我喜欢斯万特的回答。我的版本:

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

这是我的版本。这只是一个快速上升。我肯定不是很好。

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

我试过了。:)

如果有人想评论和告诉我这个解决方案有多糟糕或好,我会非常感激。我不是 非常 精通哈斯克尔。

编辑:根据KMC关于haskell blah的建议进行改进

编辑2:现在可以接受长度小于5的输入列表。

另一 一行 解决方案:

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