× {{alert.msg}} Never ask again
Get notified about new tutorials RECEIVE NEW TUTORIALS

Decide(in Haskell) if a number is or not a palindrome without using lists

Carsten König
Jul 17, 2015
<p>Ok, this is indeed a bit tricky and more math than Haskell so let's look at a possible solution (assuming a decimal system).</p> <p>The idea is to use <code>div</code> and <code>mod</code> to get at the highest and lowest digit of a number. Remember that you can write </p> <pre><code>(q,r) = n `divMod` m </code></pre> <p>to get numbers <code>q</code> and <code>r</code> so that <code>q * m + r = n</code> with <code>0 &lt;= r &lt; q</code>. For <code>m = 10</code> this will conveniently get (for positive <code>n</code>):</p> <ul> <li>in <code>q</code> all but the last digits</li> <li>in <code>r</code> the last digit</li> </ul> <p><strong>remark</strong>: I had this wrong for some time - I hope it's correct now - the edge cases are really tricky.</p> <pre><code>palindrome :: Integer -&gt; Bool palindrome n = palin n (digits n) where palin x dgts | x &lt; 0 = False | x == 0 = True | x &lt; 10 = dgts == 1 | otherwise = q == x `mod` 10 &amp;&amp; palin inner (dgts-2) where inner = r `div` 10 (q,r) = x `divMod` size size = 10^(dgts-1) digits :: Integer -&gt; Integer digits x | x &lt; 10 = 1 | otherwise = 1 + digits (x `div` 10) </code></pre> <p>Obvious I did not know the size of your problem so <code>digits</code> will look for the number of digits:</p> <ul> <li>digits 5445 = 4</li> <li>digits 123 = 3</li> <li>...</li> </ul> <p>The edge cases are these:</p> <pre><code> | x &lt; 0 = False | x == 0 = True | x &lt; 10 = digits == 1 </code></pre> <ul> <li>Obvious negative numbers should not be palindromes</li> <li>if all digits are 0 then it's an palindrome</li> <li>one-digit numbers are palindromes if indeed we are looking only at length 1 (this had me bad, as the <code>inner</code> of stuff like <code>1011</code> is a one digit nubmer <code>1</code>)</li> </ul> <p>The rest is based on this observations:</p> <ul> <li><code>x div 10^(digits-1)</code> = the highest digit (<code>5445 div 1000 = 5</code>)</li> <li><code>x mod 10^(digits-1)</code> = all but the highest digit (<code>5445 mod 1000 = 445</code>)</li> <li><code>x mod 10</code> = the lowest digit (<code>5445 mod 10 = 5</code>)</li> <li><code>number div 10</code> = remove the lowest digit (<code>5445 div 10 = 544</code>)</li> </ul> <h3>just to be safe let's test it using Quickcheck:</h3> <p>Let's use Quickcheck to test it (should be a nice example :D )</p> <pre><code>module Palindrome where import Test.QuickCheck main :: IO () main = do checkIt palindrome palindrome :: Integer -&gt; Bool palindrome n = palin n (digits n) where palin x dgts | x &lt; 0 = False | x == 0 = True | x &lt; 10 = dgts == 1 | otherwise = q == x `mod` 10 &amp;&amp; palin inner (dgts-2) where inner = r `div` 10 (q,r) = x `divMod` size size = 10^(dgts-1) digits :: Integer -&gt; Integer digits x | x &lt; 10 = 1 | otherwise = 1 + digits (x `div` 10) checkIt :: (Integer -&gt; Bool) -&gt; IO () checkIt p = quickCheckWith more (\n -&gt; n &lt; 0 || p n == (reverse (show n) == show n)) where more = stdArgs { maxSuccess = 10000, maxSize = 999999 } </code></pre> <p>seems ok:</p> <pre><code>runghc Palindrom.hs +++ OK, passed 10000 tests. </code></pre> <p>This tip was originally posted on <a href="http://stackoverflow.com/questions/26315917/Decide(in%20Haskell)%20if%20a%20number%20is%20or%20not%20a%20palindrome%20without%20using%20lists/26316343">Stack Overflow</a>.</p>
comments powered by Disqus