格雷特函数定义

我想定义一个更大的函数，它从比之前的列表项大的列表项中进行选择。

例如：

greaters [1,3,2,4,3,4,5] == [3,4,4,5]
greaters [5,10,6,11,7,12] == [10,11,12]

我想出的定义是这样的：

greaters :: Ord a => [a] -> [a]

到目前为止我尝试过的事情：

greaters (x:xs) = group [ d | d <- xs, x < xs ]

有小费吗？

我们可以推导出一个foldr基于的解决方案，从手卷递归解决方案开始进行一系列重写接受的答案:

greaters :: Ord a => [a] -> [a]
greaters [] = []
greaters (x:xs) = go x xs          -- let's re-write this clause
  where
    go _ [] = []
    go last (act:xs)
      | last < act  =  act : go act xs
      | otherwise   =        go act xs

greaters (x:xs) = go xs x          -- swap the arguments
  where
    go [] _ = []
    go (act:xs) last
      | last < act  =  act : go xs act 
      | otherwise   =        go xs act 

greaters (x:xs) = foldr g z xs x   -- go ==> foldr g z
  where
    foldr g z [] _ = []
    foldr g z (act:xs) last
      | last < act  =  act : foldr g z xs act 
      | otherwise   =        foldr g z xs act 

greaters (x:xs) = foldr g z xs x
  where                          -- simplify according to
    z _ = []                     --   foldr's definition
    g act (foldr g z xs) last 
      | last < act  =  act : foldr g z xs act 
      | otherwise   =        foldr g z xs act 

因此，最后一次重写foldr g z xs ==> r,

greaters (x:xs) = foldr g z xs x
  where
    z = const []
    g act r last
      | last < act  =  act : r act 
      | otherwise   =        r act 

额外的参数用作state当我们沿着输入列表前进时，状态是前一个元素；从而避免了施工zip具有相同目的的移位对列表。