https://wiki.haskell.org/api.php?action=feedcontributions&user=Mico+wr&feedformat=atomHaskellWiki - User contributions [en]2021-07-25T08:52:56ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=99_questions/Solutions/5&diff=5916199 questions/Solutions/52014-12-18T15:46:58Z<p>Mico wr: Added foldr solution</p>
<hr />
<div>(*) Reverse a list.<br />
<br />
<haskell><br />
reverse :: [a] -> [a]<br />
reverse = foldl (flip (:)) []<br />
</haskell><br />
<br />
The standard definition, found in the prelude, is concise, but not very readable. Another way to define reverse is:<br />
<br />
<haskell><br />
reverse :: [a] -> [a]<br />
reverse [] = []<br />
reverse (x:xs) = reverse xs ++ [x]<br />
</haskell><br />
<br />
However this definition is more wasteful than the one in Prelude as it repeatedly reconses the result as it is accumulated. The following variation avoids that, and thus computationally closer to the Prelude version.<br />
<br />
<haskell><br />
reverse :: [a] -> [a]<br />
reverse list = reverse' list []<br />
where<br />
reverse' [] reversed = reversed<br />
reverse' (x:xs) reversed = reverse' xs (x:reversed)<br />
</haskell><br />
<br />
And my favorite, although the most unreadable for sure :)<br />
<br />
<haskell><br />
myReverse'' :: [a] -> [a]<br />
myReverse'' xs = foldr (\x fId empty -> fId (x : empty)) id xs []<br />
<br />
[[Category:Programming exercise spoilers]]</div>Mico wrhttps://wiki.haskell.org/index.php?title=99_questions/Solutions/31&diff=5700399 questions/Solutions/312013-10-15T22:27:45Z<p>Mico wr: </p>
<hr />
<div>(**) Determine whether a given integer number is prime.<br />
<br />
Well, a natural number ''k'' is a prime number if it is larger than '''1''' and no natural number ''n >= 2'' with ''n^2 <= k'' is a divisor of ''k''. However, we don't actually need to check all natural numbers ''n <= sqrt k''. We need only check the '''''primes''' p <= sqrt k'':<br />
<br />
<haskell><br />
isPrime :: Integral a => a -> Bool<br />
isPrime k = k > 1 &&<br />
foldr (\p r -> p*p > k || k `rem` p /= 0 && r)<br />
True primesTME<br />
</haskell><br />
<br />
This uses<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -O2 -fno-cse #-}<br />
-- tree-merging Eratosthenes sieve<br />
-- producing infinite list of all prime numbers<br />
primesTME = 2 : gaps 3 (join [[p*p,p*p+2*p..] | p <- primes'])<br />
where<br />
primes' = 3 : gaps 5 (join [[p*p,p*p+2*p..] | p <- primes'])<br />
join ((x:xs):t) = x : union xs (join (pairs t))<br />
pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t<br />
gaps k xs@(x:t) | k==x = gaps (k+2) t <br />
| True = k : gaps (k+2) xs<br />
</haskell><br />
<br />
<br />
The tree-merging Eratosthenes sieve here seems to strike a good balance between efficiency and brevity. More at [[Prime numbers]] haskellwiki page. The semi-standard <code>union</code> function is readily available from <hask>Data.List.Ordered</hask>&nbsp;package, put here just for reference:<br />
<br />
<br />
<haskell><br />
-- duplicates-removing union of two ordered increasing lists<br />
union (x:xs) (y:ys) = case (compare x y) of <br />
LT -> x : union xs (y:ys)<br />
EQ -> x : union xs ys <br />
GT -> y : union (x:xs) ys<br />
</haskell><br />
<br />
Here is another solution, intended to be extremely short while still being reasonably fast.<br />
<br />
<haskell><br />
isPrime :: (Integral a) => a -> Bool<br />
isPrime n | n < 4 = n > 1<br />
isPrime n = all ((/=0).mod n) $ 2:3:[x + i | x <- [6,12..s], i <- [-1,1]]<br />
where s = floor $ sqrt $ fromIntegral n<br />
</haskell><br />
<br />
This one does not go as far as the previous, but it does observe the fact that you only need to check numbers of the form 6k +/- 1 up to the square root. And according to some quick tests (nothing extensive) this version can run a bit faster in some cases, but slower in others; depending on optimization settings and the size of the input.<br />
<br />
''There is a subtle bug in the version above. I'm new here (the wiki and the language) and don't know how corrections are best made (here, or on discussion?). Anyway, the above version will fail on 25, because the bound of s is incorrect. It is x+i that is bounded by the sqrt of the argument, not x. This version will work correctly:''<br />
<br />
<haskell><br />
isPrime n | n < 4 = n /= 1 <br />
isPrime n = all ((/=0) . mod n) $ takeWhile (<= m) candidates <br />
where candidates = (2:3:[x + i | x <- [6,12..], i <- [-1,1]])<br />
m = floor . sqrt $ fromIntegral n<br />
</haskell></div>Mico wrhttps://wiki.haskell.org/index.php?title=99_questions/Solutions/31&diff=5699499 questions/Solutions/312013-10-14T11:17:06Z<p>Mico wr: </p>
<hr />
<div>(**) Determine whether a given integer number is prime.<br />
<br />
Well, a natural number ''k'' is a prime number if it is larger than '''1''' and no natural number ''n >= 2'' with ''n^2 <= k'' is a divisor of ''k''. However, we don't actually need to check all natural numbers ''n <= sqrt k''. We need only check the '''''primes''' p <= sqrt k'':<br />
<br />
<haskell><br />
isPrime :: Integral a => a -> Bool<br />
isPrime k = k > 1 &&<br />
foldr (\p r -> p*p > k || k `rem` p /= 0 && r)<br />
True primesTME<br />
</haskell><br />
<br />
This uses<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -O2 -fno-cse #-}<br />
-- tree-merging Eratosthenes sieve<br />
-- producing infinite list of all prime numbers<br />
primesTME = 2 : gaps 3 (join [[p*p,p*p+2*p..] | p <- primes'])<br />
where<br />
primes' = 3 : gaps 5 (join [[p*p,p*p+2*p..] | p <- primes'])<br />
join ((x:xs):t) = x : union xs (join (pairs t))<br />
pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t<br />
gaps k xs@(x:t) | k==x = gaps (k+2) t <br />
| True = k : gaps (k+2) xs<br />
</haskell><br />
<br />
<br />
The tree-merging Eratosthenes sieve here seems to strike a good balance between efficiency and brevity. More at [[Prime numbers]] haskellwiki page. The semi-standard <code>union</code> function is readily available from <hask>Data.List.Ordered</hask>&nbsp;package, put here just for reference:<br />
<br />
<br />
<haskell><br />
-- duplicates-removing union of two ordered increasing lists<br />
union (x:xs) (y:ys) = case (compare x y) of <br />
LT -> x : union xs (y:ys)<br />
EQ -> x : union xs ys <br />
GT -> y : union (x:xs) ys<br />
</haskell><br />
<br />
Here is another solution, intended to be extremely short while still being reasonably fast.<br />
<br />
<haskell><br />
isPrime :: (Integral a) => a -> Bool<br />
isPrime n | n < 4 = n > 1<br />
isPrime n = all ((/=0).mod n) $ 2:3:[x + i | x <- [6,12..s], i <- [-1,1]]<br />
where s = floor $ sqrt $ fromIntegral n<br />
</haskell><br />
<br />
This one does not go as far as the previous, but it does observe the fact that you only need to check numbers of the form 6k +/- 1 up to the square root. And according to some quick tests (nothing extensive) this version can run a bit faster in some cases, but slower in others; depending on optimization settings and the size of the input.<br />
<br />
''There is a subtle bug in the version above. I'm new here (the wiki and the language) and don't know how corrections are best made (here, or on discussion?). Anyway, the above version will fail on 25, because the bound of s is incorrect. It is x+i that is bounded by the sqrt of the argument, not x. This version will work correctly:''<br />
<br />
<haskell><br />
isPrime n | n < 4 = n /= 1 <br />
isPrime n = all ((/=0) . mod n) $ takeWhile (<= m) candidates <br />
where candidates = (2:3:[x + i | x <- [6,12..], i <- [-1,1]])<br />
m = floor . sqrt $ fromIntegral n<br />
</haskell><br />
<br />
<br />
A simple solution...<br />
<haskell><br />
isPrime :: Int -> Bool<br />
isPrime n = all (\x -> n `mod`x /= 0) [2..sqr]<br />
where sqr = floor (sqrt (fromIntegral n :: Double))<br />
</haskell></div>Mico wrhttps://wiki.haskell.org/index.php?title=Talk:99_questions/Solutions/31&diff=56993Talk:99 questions/Solutions/312013-10-14T11:15:00Z<p>Mico wr: </p>
<hr />
<div>Does something as simple but as dump as this should be on the wiki ?<br />
<haskell><br />
isPrime :: Int -> Bool<br />
isPrime n | n <= 1 = False<br />
isPrime n = isPrime' 2 n<br />
where isPrime' x n | x*x > n = True<br />
| otherwise = (n `rem` x) /= 0 && isPrime' (x+1) n<br />
</haskell><br />
<br />
== And something as simple as this one... ==<br />
<br />
<haskell><br />
isPrime :: Int -> Bool<br />
isPrime n = all (\x -> n `mod`x /= 0) [2..sqr]<br />
where sqr = floor (sqrt (fromIntegral n :: Double))<br />
</haskell><br />
-- Assuming that a number is not a prime if he is divisible by any number between 2 and his sqrt</div>Mico wrhttps://wiki.haskell.org/index.php?title=Talk:99_questions/Solutions/31&diff=56992Talk:99 questions/Solutions/312013-10-14T11:14:06Z<p>Mico wr: /* And something as simple as this one... */ new section</p>
<hr />
<div>Does something as simple but as dump as this should be on the wiki ?<br />
<haskell><br />
isPrime :: Int -> Bool<br />
isPrime n | n <= 1 = False<br />
isPrime n = isPrime' 2 n<br />
where isPrime' x n | x*x > n = True<br />
| otherwise = (n `rem` x) /= 0 && isPrime' (x+1) n<br />
</haskell><br />
<br />
== And something as simple as this one... ==<br />
<br />
isPrime :: Int -> Bool<br />
isPrime n = all (\x -> n `mod`x /= 0) [2..sqr]<br />
where sqr = floor (sqrt (fromIntegral n :: Double))<br />
<br />
-- Assuming that a number is not a prime if he is divisible by any number between 2 and his sqrt</div>Mico wr