3

これは、ここ数日間夢中になっている宿題です。

関数を適用しているリストを取得しました。隣の要素が前の要素よりも小さい場合は、各要素を右に押します。

リストを一度渡してリストの先頭をソートする私の関数：

sortEm lis@(x:y:xs) = if x > y then y: sortEm (x:xs) else lis
sortEm [x] = [x]
sortEm [] = []

myList (x:y:xs) = if x > y then sortEm lis else x:myList(y:xs)
myList [] = []
myList [x] = [x]

しかし、私の問題は、そのsortemが終了すると、空のリストまたは1つの要素を含むリストのいずれかが返されることです。これを機能的に設計するにはどうすればよいですか？

foldlとそれに伴うhaskellの魔法について考えていましたが、現在は行き詰まっています。

前もって感謝します

4

3 に答える 3

4

まず、sortEm関数名は誤解を招く可能性があります。引数リストは並べ替えられませんが、head要素がtailに挿入されます。たまたま、最初の引数を2番目の引数に挿入するinsert関数がすでにData.Listモジュールにあるので、同等性があります

sortEm (x:xs) === Data.List.insert x xs

現在、アイテムを挿入すると、既に並べ替えられているリストにアイテムを挿入している場合にのみ、並べ替えられたリストが返されます。空のリストがソートされているので、それmyListはあなたがdave4420の答えで得た関数です。これは「挿入」ソートであり、リストの要素を補助リストに徐々に挿入しますが、最初は空です。そして、それはあなたがdave4420の答えで得た2番目の関数が行うことです：

insertionSort xs = foldr Data.List.insert [] xs

これは「sortemを適用」します。つまり、「各要素」を1回だけ挿入します。リスト[a,b,c,...,z]の場合、それはと同等です

insert a (insert b (insert c (... (insert z []) ...)))

コメントでおそらく意味したこと、つまり、2つの隣接する要素を「一度だけ」比較する（場合によっては交換する）ことは、バブルソートとして知られています。もちろん、一般的なケースでは、リストを1回だけパスしても、ソートされません。

bubbleOnce xs = foldr g [] xs  where
  g x [] = [x]
  g x xs@(y:ys) | x>y       = y:x:ys  -- swap x and y in the output
                | otherwise = x:xs    -- keep x before y in the output

さて、bubbleOnce [4,2,6,1,8] ==> [1,4,2,6,8]。期待した値は、左から右への反対方向に[2,4,1,6,8]折りたたみ関数を適用した結果です。しかし、ここでHaskellリストを使用するのはそれほど自然ではありません。g

bubbleOnce' [] = []
bubbleOnce' (x:xs) = let (z,h)=foldl g (x,id) xs in (h [z])  where
  g (x,f) y | x>y       = (x, f.(y:))   -- swap x and y in the output
            | otherwise = (y, f.(x:))   -- keep x before y in the output

（編集:)同等であるが、単純な再帰を使用した単純で優れたバージョンについては、jimmytの回答を参照してください。fodlrまた、ここのバージョンとバージョンの両方よりも怠惰です（厳密ではありません）foldl。

于 2012-06-12T09:07:15.787 に答える
2 
myList []       = []
myList (x : xs) = sortEm (x : myList xs)

（未テスト）

またはフォールドの観点から：

myList = foldr cons []
  where cons x xs = sortEm (x : xs)

（これもテストされていません）

于 2012-06-11T22:25:27.630 に答える
2 
-- if..then..else version
sortEM      ::  Ord a => [a] -> [a]

sortEM (x:y:xs)     =   if x < y
                        then x : sortEM (y:xs)
                        else y : sortEM (x:xs)
sortEM b            =   b   


-- guard version
sortEM_G    ::  Ord a => [a] -> [a]

sortEM_G (x:y:xs)
     | x < y        =   x : sortEM_G (y:xs)
     | otherwise    =   y : sortEM_G (x:xs)
sortEM_G b          =   b
于 2012-06-12T12:57:56.757 に答える