1

リストのリスト ([[a]]) を返すが、空のリスト ([]:[a]) を使用しない場合の構文は (可能な場合) でしょうか? (下の 2 番目にコメントされたガード (2) に似ていますが、これは正しくありません)

これは正しく動作する関数です:

-- Split string on every (shouldSplit == true)
splitWith :: (Char -> Bool) -> [Char] -> [[Char]]
splitWith shouldSplit list = filter (not.null) -- would like to get rid of filter
  (imp' shouldSplit list)
  where 
    imp' _ [] = [[]]
    imp' shouldSplit (x:xs)
      | shouldSplit x  = []:imp' shouldSplit xs  -- (1) this line is adding empty lists
--      | shouldSplit x  = [imp' shouldSplit xs]   -- (2) if this would be correct, no filter needed
      | otherwise  = let (z:zs) = imp' shouldSplit xs in (x:z):zs

これが正しい結果です

Prelude> splitWith (== 'a') "miraaaakojajeja234"
["mir","koj","jej","234"]

ただし、結果をクリーンアップするには「フィルター」を使用する必要があるため、関数「フィルター」を削除したいと考えています。これは、フィルターを使用しない場合の結果です。

["mir","","","","koj","jej","234"]

最初のガードの代わりに" | shouldSplit x = imp' shouldSplit xs " を使用すると、結果は正しくありません。

["mirkojjej234"]

最初のガード (1) は空のリストを追加するため、コンパイラは結果をリストのリスト ([[a]]) として扱うことができると思います。

（関数の別の/異なるソリューションには興味がありません。構文の明確化だけです。）

.
.
.

答え:

Dave4420 からの回答で回答が得られましたが、回答ではなくコメントだったので、回答として受け入れることはできません。問題の解決策は、私が間違った質問をしているということでした。これは構文の問題ではなく、私のアルゴリズムの問​​題です。

空のリストの問題を解決する別の/異なるソリューションにはいくつかの回答がありますが、それらは私の質問に対する回答ではありません。しかし、彼らは、基本的な Haskell 構文を使って物事を行う方法について、私の見解を広げてくれました。私は彼らに感謝しています。

編集：

splitWith :: (Char -> Bool) -> String -> [String]
splitWith p = go False
  where 
    go _ [] = [[]]
    go lastEmpty (x:xs)
      | p x        = if lastEmpty then go True xs else []:go True xs
      | otherwise  = let (z:zs) = go False xs in (x:z):zs
4

4 に答える 4

3

これは、パターン マッチングを利用して、1 回のトラバーサルで空のインターリーブ リストを生成しないというタスクを完了します。

splitWith :: Eq a => (a -> Bool) -> [a] -> [[a]]
splitWith f list = case splitWith' f list of
  []:result -> result
  result -> result
  where
    splitWith' _ [] = []
    splitWith' f (a:[]) = if f a then [] else [[a]]
    splitWith' f (a:b:tail) =
      let next = splitWith' f (b : tail)
      in if f a
        then if a == b
          then next
          else [] : next
        else case next of
          [] -> [[a]]
          nextHead:nextTail -> (a : nextHead) : nextTail

それを実行する：

main = do
  print $ splitWith (== 'a') "miraaaakojajeja234"
  print $ splitWith (== 'a') "mirrraaaakkkojjjajeja234"
  print $ splitWith (== 'a') "aaabbbaaa"

プロデュース:

["mir","koj","jej","234"]
["mirrr","kkkojjj","jej","234"]
["bbb"]
于 2013-03-11T15:10:32.960 に答える
2

この問題は、分割しているリストの折り畳みとして非常に自然に表現されます。結果リストと、結果リストに追加するために構築されている現在の単語の 2 つの状態を追跡する必要があります。

私はおそらく次のような素朴なバージョンを書くでしょう：

splitWith p xs = word:result
    where
        (result, word)        = foldr func ([], []) xs
        func x (result, word) = if p x
            then (word:result,[])
            else (result, x:word)

predicate を満たす新しい要素を検出するたびに現在の単語を結果に追加するため、これも空のリストに残ることに注意してくださいp。

これを修正するには、リスト コンス演算子(:)を新しい演算子に置き換えるだけです

(~:) :: [a] -> [[a]] -> [[a]]

元のリストが空でない場合にのみ、あるリストを別のリストに変換します。残りのアルゴリズムは変更されていません。

splitWith p xs = word ~: result
    where
        (result, word)        = foldr func ([], []) xs
        func x (result, word) = if p x
            then (word ~: result, [])
            else (result, x:word)
        x ~: xs = if null x then xs else x:xs

それはあなたが望むことをします。

于 2013-03-11T15:03:27.410 に答える
1

私はクリスと似たような考えを持っていたと思います。

splitWith shouldSplit list = imp' list [] []
  where 
    imp' [] accum result = result ++ if null accum then [] else [accum]
    imp' (x:xs) accum result
      | shouldSplit x  = 
          imp' xs [] (result ++ if null accum 
                                   then [] 
                                   else [accum])
      | otherwise  = imp' xs (accum ++ [x]) result
于 2013-03-11T15:11:31.927 に答える
1

これは基本的に、 と を交互に適用しただけですdropWhile。breakそうではありません。

splitWith p xs = g xs
   where
     g xs = let (a,b) = break p (dropWhile p xs)
            in if null a then [] else a : g b

あなたは自分のソリューション以外には興味がないと言いますが、他の読者は興味があるかもしれません。それは確かに短く、はっきりと見えます。学習するにつれて、基本的なPrelude機能を使用することが第二の性質になります。:)

あなたのコードに関しては、本質的ではない方法で少し作り直されています（「述語」やメインワーカー関数のようpに、短い示唆的な関数名を使用しています）、それはg

splitWith :: (Char -> Bool) -> [Char] -> [[Char]]
splitWith p list = filter (not.null) (g list)
  where 
    g  [] = [[]]
    g (x:xs)
      | p x  = [] : g xs  
      | otherwise  = let (z:zs) = g xs 
                     in (x:z):zs

また、述語を引数としてワーカーに渡す必要はありません (コメントにも記載されています)。これで、間違いなくもう少し読みやすくなりました。

次に、最小限の変更で、

splitWith :: (Char -> Bool) -> [Char] -> [[Char]]
splitWith p list = case g list of ([]:r)-> r; x->x
  where 
    g  [] = [[]]
    g (x:xs)
      | p x  = case z of []-> r;    -- start a new word IF not already
                         _ -> []:r  
      | otherwise  = (x:z):zs
           where                    -- now z,zs are accessible
             r@(z:zs) = g xs        -- in both cases

あなたが望むように動作します。トップレベルcaseでは、ここで最大 1 つの空の単語を削除しています。これは、内部関数の作業中のある時点で区切り記号として機能します。ここでは基本的に、新しい単語の条件付き開始1 (つまり、空のリストの追加1filter (not.null) ) を使用してワーカー関数に融合されます。g

letyourをwhere変数 (など) に置き換えると、定義zの 2 番目の句の両方のブランチでアクセスできるようになりました。g

最終的に、あなたのアルゴリズムは十分に近く、コードを修正することができました。

「右から左」と考える場合は1 。実際には、リストは左から右に、保護再帰 ⁄末尾再帰 modulo cons方式で構築されます。

于 2013-03-13T00:40:40.620 に答える