この単語機能の実装は、折りたたんだ後の後処理ステップなしで可能ですか?

21
Enlico 2020-04-29 21:22.

Real World Haskell、第4章、98ページの印刷物は、words折り目を使用して実装できるかどうかを尋ねています。これも私の質問です。

出来ますか?そうでない場合、なぜですか?もしそうなら、どのように?

私は次のことを思いつきました。これは、各非スペースを出力リストの最後の単語の前に追加する必要があり(これはotherwiseガードで発生します)、スペースは空の単語の追加をトリガーする必要があるという考えに基づいています。出力リストがまだ存在しない場合(これがで取り扱われますif- - )。thenelse

myWords :: String -> [String]
myWords = foldr step [[]]
  where
    step x [email protected](y:ys)
      | x == ' ' = if y == "" then yss else "":yss
      | otherwise = (x:y):ys

入力文字列の先頭のスペースにより、文字列の出力リストに1つの先頭の空の文字列が生成されるため、この解決策は明らかに間違っています。

上記のリンクで、私は他の読者のために提案された解決策のいくつかに見てきた、として、インスタンスのために、倍の出力を、それらの多くは、私の解決策と同様に動作しますが、彼らは一般的に「後処理」tailがあった場合、それをINGの空の先頭文字列です。

他のアプローチではタプル(実際にはペアのみ)を使用するため、フォールドはペアを処理し、先頭/末尾のスペースを適切に処理できます。

これらすべてのアプローチfoldr(または別のフォールド、fwiw)は、箱から出して最終出力を提供する関数ではありません。どういうわけか出力を調整しなければならない何か他のものが常にあります。

したがって、最初の質問に戻って、words折り目を使用して(末尾/先頭/繰り返しスペースを正しく処理する方法で)実際に実装できるかどうかを尋ねます。折り目を使用して、私は折りたたみ機能は、最も外側の関数でなければならないことを意味します。

myWords :: String -> [String]
myWords input = foldr step seed input

3 answers

15
chi 2020-04-29 21:36.

私が正しく理解している場合、あなたの要件には以下が含まれます

(1) words "a b c" == words " a b c" == ["a", "b", "c"]
(2) words "xa b c" == ["xa", "b", "c"] /= ["x", "a", "b", "c"] == words "x a b c"

これは私たちが持つことができないことを意味します

words = foldr step base

任意のためstepbase

確かに、それがあれば、

words "xa b c"
= def words and foldr
step 'x' (words "a b c")
= (1)
step 'x' (words " a b c")
= def words and foldr
words "x a b c"

そしてこれは(2)と矛盾します。

後処理は間違いなく必要foldrです。

6
luqui 2020-04-29 22:26.

@chiには、words「a」フォールドを使用して実装できないという素晴らしい議論がありますが、フォールドsを使用して言ったです。

words = filterNull . words1
    where
    filterNull = foldr (\xs -> if null xs then id else (xs:)) []
    words1 = foldr (\c -> if c == ' ' then ([]:) else consHead c) []
    consHead c []       = [[c]]
    consHead c (xs:xss) = (c:xs):xss

最も外側と最も内側の機能は両方とも折り目です。;-)

2
Redu 2020-05-01 04:25.

はい。少し注意foldrが必要ですが、CPS(継続渡しスタイル)にこだわる場合は、1つだけを使用してこの作業を適切に行うことができます。私はchunksOf以前に特別な種類の機能を示しました。

この種のフォールドでは、アキュムレータ、したがってフォールドの結果は関数であり、最終的な結果が得られるように、それをアイデンティティの種類の入力に適用する必要があります。したがって、ここでは1つのフォールドを使用しており、そのタイプには関数が含まれているため、これは最終処理段階としてカウントされる場合とされない場合があります。議論の余地あり:)

ws :: String -> [String]
ws str = foldr go sf str $ ""
         where
         sf :: String -> [String]
         sf s = if s == " " then [""] else [s]
         go :: Char -> (String -> [String]) -> (String -> [String])
         go c f = \pc -> let (s:ss) = f [c]
                         in case pc of
                            ""        -> dropWhile (== "") (s:ss)
                            otherwise -> case (pc == " ", s == "") of
                                         (True, False)  -> "":s:ss
                                         (True, True)   -> s:ss
                                         otherwise      -> (pc++s):ss

λ> ws "   a  b    c   "
["a","b","c"]

sf :最初の関数の初期値。

go :イテレータ機能

前のキャラクターpcと現在のキャラクターの両方cが毎ターン手元にあるため、実際にはここではCPSの力を十分に活用していません。昇順の要素シーケンスが壊れるたびにchunksOfをチャンク[Int][[Int]]するときに、上記の関数で非常に役立ちました。

Related questions

MORE COOL STUFF

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire が息子の Shelby Blackstock と共有しているクリスマスの伝統について学びましょう。

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルとマライア・キャリーが自然な髪の上でどのように結合したかについて、メーガンの「アーキタイプ」ポッドキャストのエピソードで学びましょう.

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子が家族、特にチャールズ王とウィリアム王子との関係について望んでいると主張したある情報源を発見してください。

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドが、母親のナオミ・ジャッドが亡くなってから初めての感謝祭のお祝いを主催しているときに、彼女が今では家長であることをどのように認識したかを学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

2017年の最も人気のある投稿

2017年の最も人気のある投稿

ここLifehackerでは大きな年でした。一緒に、私たちはミツバチを救おうとし、ハッキングされ、太陽をじっと見つめ、グロスチェーンレストランの食べ物を食べ、核爆弾から身を隠しました。

ラストコール:素晴らしき人生だ、コーシャワイン、そしてジュリアチャイルドはユールログを作るのが苦手

ラストコール:素晴らしき人生だ、コーシャワイン、そしてジュリアチャイルドはユールログを作るのが苦手

写真:ゲッティイメージズ経由のハーバート・ドーフマン/コービスさて、昨日、幼い子供たちにマジシャンズを見させて銃を飛び越えていたようです。知っておくと良い!昨夜、娘と私はシカゴの素晴らしいビンテージシアターであるミュージックボックスで映画を見に行きました。年齢に関係なく、誰も問題を抱えてはいけません。それは素晴らしい人生です。

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

Tomorrow's Kitchen シリコンストレッチ蓋 12個パック | $14 | アマゾン | プロモーション コード 20OFFKINJALids は基本的にキッチンの靴下です。常に迷子になり、二度と閉じられない孤立したコンテナーが残ります。しかし、蓋が伸びて、残った容器、鍋、フライパン、さらには大きなスライスされた果物のすべてに適合するとしたらどうでしょうか? その非常に特殊な蓋を失うことを二度と心配する必要はありません。

あなたの最高のワシントン DC ハックを教えてください

あなたの最高のワシントン DC ハックを教えてください

このコラムでは、ロサンゼルスやラスベガスなど、いくつかの産業都市をハッキングしました。今こそ、軍産複合都市の時代です。

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

ロシアのフィギュアスケーター、カミラ・バリエバが関与したドーピング事件が整理されているため、チームは2022年北京冬季オリンピックで獲得したメダルを待っています。

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

何千人ものAmazonの買い物客がMulberry Silk Pillowcaseを推奨しており、現在販売中. シルクの枕カバーにはいくつかの色があり、髪を柔らかく肌を透明に保ちます。Amazonで最大46%オフになっている間にシルクの枕カバーを購入してください

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

ラファイエット警察署は、「不審な男性が女性に近づいた」という複数の苦情を受けて、12 月にパデュー大学の教授の捜査を開始しました。

コンセプト ドリフト: AI にとって世界の変化は速すぎる

コンセプト ドリフト: AI にとって世界の変化は速すぎる

私たちの周りの世界と同じように、言語は常に変化しています。以前の時代では、言語の変化は数年または数十年にわたって発生していましたが、現在では数日または数時間で変化する可能性があります。

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

犯罪擁護派のオークランドが暴力犯罪者のロミオ・ロレンゾ・パーハムを釈放

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

認知症を患っている 91 歳のアジア人女性が最近、47 番街のアウター サンセット地区でロメオ ロレンゾ パーハムに襲われました。伝えられるところによると、被害者はサンフランシスコの通りを歩いていたところ、容疑者に近づき、攻撃を受け、暴行を受けました。

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Cómo mejoramos la accesibilidad de nuestro componente de precio, y cómo nos marcó el camino hacia nuevos saberes para nuestro sistema de diseño. Por Ana Calderon y Laura Sarmiento Leer esta historia en inglés.

ℝ

“And a river went out of Eden to water the garden, and from thence it was parted and became into four heads” Genesis 2:10. ? The heart is located in the middle of the thoracic cavity, pointing eastward.

Language