2

次のようなリストがあるとします。

[4,5,6,7,1,2,3,4,5,6,1,2]

このリストを昇順でシリーズを形成する元のリストのセグメントで構成されるリストのリストに変換する Haskell 関数が必要です。したがって、結果は次のようになります。

[[4,5,6,7],[1,2,3,4,5,6],[1,2]]

助言がありますか？

4

5 に答える 5

8

手動再帰に頼ることでこれを行うことができますが、Haskell はより進化した言語であると私は信じています。既存の再帰戦略を使用するソリューションを開発できるかどうか見てみましょう。まずは予備編。

{-# LANGUAGE NoMonomorphismRestriction #-}
-- because who wants to write type signatures, amirite?
import Data.List.Split -- from package split on Hackage

ステップ 1 は、リストの 2 つの要素を一度に見る基準に基づいて、リストを分割したいことを確認することです。そのため、「前の」値と「次の」値を表す要素を含む新しいリストが必要になります。これには非常に標準的なトリックがあります。

previousAndNext xs = zip xs (drop 1 xs)

しかし、私たちの目的では、これはうまくいきません: この関数は常に入力よりも短いリストを出力し、常に入力と同じ長さのリストが必要です (特に、入力は長さ 1 のリストです)。そこで、「ヌル ターミネータ」を使用して、標準のトリックを少し変更します。

pan xs = zip xs (map Just (drop 1 xs) ++ [Nothing])

このリストを調べて、前の要素が次の要素よりも大きい (または次の要素が存在しない) 場所を探します。そのチェックを行う述語を書きましょう。

bigger (x, y) = maybe False (x >) y

実際に分割を行う関数を書きましょう。「区切り文字」はbigger、 ;を満たす値になります。絶対に捨てたくないので、大切に保管しましょう。

ascendingTuples = split . keepDelimsR $ whenElt bigger

最後のステップは、タプルを構築するビット、タプルを分割するビット、そして気にしないタプルのビットを捨てる最後のマンジを投げることです:

ascending = map (map fst) . ascendingTuples . pan

ghci で試してみましょう:

*Main> ascending [4,5,6,7,1,2,3,4,5,6,1,2]
[[4,5,6,7],[1,2,3,4,5,6],[1,2]]
*Main> ascending [7,6..1]
[[7],[6],[5],[4],[3],[2],[1]]
*Main> ascending []
[[]]
*Main> ascending [1]
[[1]]

PS の現在のリリースではsplit、keepDelimsRは必要以上に厳密であり、その結果、ascending現在、無限リストでは機能しません。ただし、怠惰にするパッチを提出しました。

于 2013-01-18T21:27:55.917 に答える
6 
ascend :: Ord a => [a] -> [[a]]
ascend xs = foldr f [] xs
  where
    f a []  = [[a]]
    f a xs'@(y:ys) | a < head y = (a:y):ys
                   | otherwise = [a]:xs'

ghciで

*Main> ascend [4,5,6,7,1,2,3,4,5,6,1,2]
[[4,5,6,7],[1,2,3,4,5,6],[1,2]]
于 2013-01-18T16:37:16.950 に答える
4

この問題は、パラモーフィズムベースのソリューションに自然に適合します。持つ（その投稿で定義されているように）

para  :: (a -> [a] -> b -> b) -> b -> [a] -> b
foldr :: (a ->        b -> b) -> b -> [a] -> b

para  c n (x : xs)  =  c x xs (para  c n xs)
foldr c n (x : xs)  =  c x    (foldr c n xs)
para  c n []        =  n
foldr c n []        =  n

私たちは書くことができます

partition_asc xs  =  para c [] xs  where
  c x (y:_) ~(a:b) | x<y  =  (x:a):b 
  c x  _      r           =  [x]:r

抽象化が適合するため、自明です。

ところで、Common Lispに は (入力リストの要素を 1 つずつ処理する) と(リストの「末尾」を処理する)の 2 種類があります。mapこのアイデアにより、mapcarmaplist

import Data.List (tails)

partition_asc2 xs  =  foldr c [] . init . tails $ xs  where
  c (x:y:_) ~(a:b) | x<y  =  (x:a):b
  c (x:_)     r           =  [x]:r

両方のバージョンの遅延パターンにより、生産的な方法で無限の入力リストを処理できます ( Daniel Fischerの回答で最初に示されているように)。

2020-05-08 更新:結局、それほど些細なことではありません。で失敗する場合は両方ともhead . head . partition_asc $ [4] ++ undefined同じです。結合関数は、次の要素を時期尚早に強制します。次の要素を見る前にすぐに生産的になるように、より慎重に記述する必要があります。たとえば、2 番目のバージョンの場合は、partition_asc2*** Exception: Prelude.undefinedgy

partition_asc2' xs  =  foldr c [] . init . tails $ xs  where
  c (x:ys) r@(~(a:b))  =  (x:g):gs
         where
         (g,gs) | not (null ys) 
                  && x < head ys =  (a,b)
                | otherwise      =  ([],r)

（繰り返しますが、ダニエルの回答で最初に示されているように）。

于 2013-01-22T03:53:18.730 に答える
3

右折を使用して、ダウンステップでリストを分割できます。

foldr foo [] xs
  where
    foo x yss = (x:zs) : ws
      where
        (zs, ws) = case yss of
                     (ys@(y:_)) : rest
                            | x < y     -> (ys,rest)
                            | otherwise -> ([],yss)
                     _ -> ([],[])

(2 番目の引数で結合関数を遅延させるのは少し複雑なので、無限リストでもうまく機能します。)

于 2013-01-18T16:37:55.600 に答える