8

私は Haskell にかなり慣れていないので、少し問題があります。リストとintを取る関数を実装しようとしています。int は、リストがリストのペアに分割されるインデックス k であると想定されています。リストの最初の k 個の要素を含む最初のものと、k+1 から最後の要素までの 2 番目のもの。これが私がこれまでに持っているものです：

split :: [a] -> Int -> ([a], [a])
split [] k = error "Empty list!"
split (x:[]) k = ([x],[])
split xs k | k >= (length xs) = error "Number out of range!"
           | k < 0 = error "Number out of range!"

私は実際に分割を行う方法を理解できません。どんな助けでも大歓迎です。

4

5 に答える 5

19

まず、作成しようとしている関数が既に標準ライブラリにあることに注意してPreludeくださいsplitAt。2 つのアルゴリズムがあり、1 つは標準の再帰構造をまったく使用せず、もうsplitAt n xs = (take n xs, drop n xs)1 つは手動で最適化されて醜くなっています。前者は、接頭辞と接尾辞を取り、それらをペアにするだけなので、より直感的に理解できます。ただし、後者はより多くを教えており、全体的な構造は次のとおりです。

splitAt :: Int -> [a] -> ([a], [a])
splitAt 0 xs     = ([], xs)
splitAt _ []     = ([], [])
splitAt n (x:xs) = (x:xs', xs'')
  where
    (xs', xs'') = splitAt (n - 1) xs

基本的な考え方は、リストが頭と尾で構成されている場合 (形式はx:xs)、インデックス k+1 以降のリストは、インデックスを削除すると k 以降のリストと同じになるということです。最初の要素 - drop (k + 1) (x : xs) == drop k xs. プレフィックスを作成するには、同様に最初の要素を削除し、より小さなプレフィックスを取り、要素を - に戻しtake (k + 1) (x : xs) == x : take k xsます。

于 2012-09-22T02:26:43.697 に答える
3

これはどうですか：

splitAt' = \n -> \xs -> (take n xs, drop n xs)

いくつかのテスト:

> splitAt' 3 [1..10]
> ([1,2,3],[4,5,6,7,8,9,10])

> splitAt' 0 [1..10]
> ([],[1,2,3,4,5,6,7,8,9,10])

> splitAt' 3 []
> ([],[])

> splitAt' 11 [1..10]
> ([1,2,3,4,5,6,7,8,9,10],[])

> splitAt' 2 "haskell"
> ("ha","skell")
于 2012-09-24T23:30:06.467 に答える
1

基本的に、リストを再帰的に処理するときに、部分的な進行状況を渡す何らかの方法が必要です。アキュムレータ パラメーターを受け取る 2 つ目の関数を使用しました。split から呼び出され、それ自体を再帰的に呼び出します。ほぼ確実にもっと良い方法があります..

編集:すべての長さチェックを削除しましたが、の使用は++まだ O(n^2) であることを意味すると思います。

split xs k | k < 0 = error "Number out of range!"
split xs k = ssplit [] xs k

ssplit p xs 0 = (p, xs)
ssplit p (x:xs) k = ssplit (p++[x]) xs (k-1)
ssplit p [] k = error "Number out of range!"

元の投稿で動作を取得するか、

ssplit p [] k = (p,[])

splitAt標準関数のより寛容な動作を取得します。

于 2012-09-22T02:21:12.233 に答える
1

リストを構築する際に 2 次動作を取り除くための一般的なトリックは、Mark Reed のソリューションを変更して、逆方向に構築してから逆にすることです。

split xs k | k < 0 = error "Number out of range!"
split xs k = (reverse a, b)
  where
    (a,b) = ssplit [] xs k

ssplit p xs 0 = (p, xs)
ssplit p (x:xs) k = ssplit (x:p) xs (k-1)
ssplit p [] k = error "Number out of range!"

ssplit のエラー チェックは、実際のエラーがない限りチェックされない (以前のパターンの 1 つが一致する) ため、問題ありません。

実際には、スタックの増加を管理するために、ssplit にいくつかの厳密性アノテーションを追加することをお勧めしますが、それはさらに洗練されたものです。

于 2012-09-24T10:51:11.323 に答える
0

splitAt前奏曲を参照してください。

ghci> :t flip splitAt
flip splitAt :: [a] -> Int -> ([a], [a])
ghci> flip splitAt  ['a'..'j'] 5
("abcde","fghij")
于 2012-09-22T02:29:59.737 に答える