2016-12-29 6 views
1

私は、数字が回文かどうかを判断する関数を書いています。文字列を最初、最後、最後にどのように破棄するのですか?

私が最初にしたいのは、文字列を最初の文字、中間のすべての文字、最後の文字に分解することです。私がするのは、最初の文字が最後の文字と等しいかどうかを確認し、そうであれば中間の文字をチェックすることです。

私が持っているものは以下ですが、コンパイル時にタイプエラーが発生します。あなたは型エラー理由を取得している[1,2]

1:2:[]結果:

numberIsPalindrome :: Int -> Bool 
numberIsPalindrome n = 
    case nString of 
    (x:xs:y) -> (x == y) && numberIsPalindrome xs 
    (x:y) -> x == y 
    x -> True 
    where nString = show n 
+0

リストは、リスト(ない配列)をリンクされている...

palindrome n = f (show n) where f [] = True f [_] = True f (x : xs) = (x == last xs) && (f (init xs)) 

をしかし、これは本当のライブで、このようなコードを使用していない、デモンストレーションの目的のためだけです、最後にアクセスするのは高価な操作であり、パターンマッチングでは実行できません。そのために 'last'ライブラリ関数を使用できますが、遅くなります。リストを逆にして、以下に示すように等価性をチェックする方がはるかに効率的で簡単です。 – chi

答えて

3

String表現が浮気された使用を...

そうでもないが、これはもっと楽しいです:

import Data.List 

palindrome n = list == reverse list where 
    list = unfoldr f n 
    f 0 = Nothing 
    f k = Just (k `mod` 10, k `div` 10) 

数字の数字のリストを作成することです(unfoldrはそのようなタスクには本当に便利です)。逆転したときにリストが同じままであるかどうか。

あなたが試したことにはいくつかの問題があります。数字からString(これはHaskellのCharのリストに過ぎません)への変換がありません。リストはあなたが試したものとはまったく異なったものです。

つまり、一覧の「外側」要素から内側の要素に移動することができるように、リストにはinitlastの機能があります。ナイーブ(非効率的な)実装は次のようになります。

+0

改善点:1。あなたがそれを構築するときにリストの長さを追跡することで、いつ比較を停止するかを知ることができます。 2. 'div'と' mod'の代わりに 'quotRem'を使います。 3.引数がゼロではなく、最下位桁がゼロであれば、直ちにfalseを返します。 4.リストからベクトルに切り替えて、割り当てとポインタの追跡を減らします。 – dfeuer

1

あなたはおそらくしたい定義が、それはリストに項目を付加、(:)オペレータはconsとして知られている

numberIsPalindrome :: Int -> Bool 
numberIsPalindrome num = let str = show num 
         in (str == reverse str) 
+4

あなたが自分のアイデアを自分のものに置き換えるのではなく、OPの述べた戦略に "はい"と答えて助けてくれるといいですね – luqui

1

です最初の引数であるCharと最後の引数である[a]を比較しようとしています。

実際に最初のものと最後のものを比較したい場合はheadlastを使用します。

しかし、あなたはより良いtaktoaが提案されたソリューションを使用している:

numberIsPalindrome :: Int -> Bool 
numberIsPalindrome num = 
    numberString == reverse numberString 
    where numberString = show num 
+0

各繰り返しで 'last'を呼び出すと、アルゴリズムはO(n^2)ではなく、O(n)であるから、 'last'はO(n)です。 – taktoa

関連する問題