https://wiki.haskell.org/api.php?action=feedcontributions&user=Ibizaman&feedformat=atomHaskellWiki - User contributions [en]2024-03-29T09:02:05ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Talk:99_questions/Solutions/31&diff=43937Talk:99 questions/Solutions/312012-01-14T09:29:31Z<p>Ibizaman: </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></div>Ibizamanhttps://wiki.haskell.org/index.php?title=Talk:99_questions/Solutions/31&diff=43936Talk:99 questions/Solutions/312012-01-14T09:27:34Z<p>Ibizaman: New page: Does something like this deserves being put on the wiki ? <haskell> isPrime :: Int -> Bool isPrime n | n <= 1 = False isPrime n = isPrime' 2 n where isPrime' x n | x*x > n = True ...</p>
<hr />
<div>Does something like this deserves being put 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></div>Ibizamanhttps://wiki.haskell.org/index.php?title=99_questions/Solutions/26&diff=4393599 questions/Solutions/262012-01-14T09:04:45Z<p>Ibizaman: </p>
<hr />
<div>(**) Generate the combinations of K distinct objects chosen from the N elements of a list<br />
<br />
In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the<br />
well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.<br />
<br />
<haskell><br />
-- Import the 'tails' function<br />
-- > tails [0,1,2,3]<br />
-- [[0,1,2,3],[1,2,3],[2,3],[3],[]]<br />
import Data.List (tails)<br />
<br />
-- The implementation first checks if there's no more elements to select,<br />
-- if so, there's only one possible combination, the empty one,<br />
-- otherwise we need to select 'n' elements. Since we don't want to<br />
-- select an element twice, and we want to select elements in order, to<br />
-- avoid combinations which only differ in ordering, we skip some<br />
-- unspecified initial elements with 'tails', and select the next element,<br />
-- also recursively selecting the next 'n-1' element from the rest of the<br />
-- tail, finally consing them together<br />
<br />
-- Using list comprehensions<br />
combinations :: Int -> [a] -> [[a]]<br />
combinations 0 _ = [ [] ]<br />
combinations n xs = [ y:ys | y:xs' <- tails xs<br />
, ys <- combinations (n-1) xs']<br />
<br />
-- Alternate syntax, using 'do'-notation <br />
combinations :: Int -> [a] -> [[a]]<br />
combinations 0 _ = return []<br />
combinations n xs = do y:xs' <- tails xs<br />
ys <- combinations (n-1) xs'<br />
return (y:ys)<br />
</haskell><br />
<br />
Another solution that's slightly longer, but doesn't depend on <hask>tails</hask>:<br />
<br />
<haskell><br />
combinations :: Int -> [a] -> [[a]]<br />
-- We don't actually need this base case; it's just here to<br />
-- avoid the warning about non-exhaustive pattern matches<br />
combinations _ [] = [[]]<br />
-- Base case--choosing 0 elements from any list gives an empty list<br />
combinations 0 _ = [[]]<br />
-- Get all combinations that start with x, recursively choosing (k-1) from the<br />
-- remaining xs. After exhausting all the possibilities starting with x, if there<br />
-- are at least k elements in the remaining xs, recursively get combinations of k<br />
-- from the remaining xs.<br />
combinations k (x:xs) = x_start ++ others<br />
where x_start = [ x : rest | rest <- combinations (k-1) xs ]<br />
others = if k <= length xs then combinations k xs else []<br />
</haskell><br />
<br />
Variant: This version avoids getting a result consisting of the empty choice if we ask for, say, 10 elements from the empty list. (Instead, an empty list, suggesting "no options available" is returned.)<br />
<haskell><br />
combinations :: Int -> [a] -> [[a]]<br />
combinations 0 _ = [[]]<br />
combinations _ [] = []<br />
combinations n (x:xs) = (map (x:) (combinations (n-1) xs)) ++ (combinations n xs)<br />
</haskell><br />
<br />
A solution using subsequences in Data.List<br />
<haskell><br />
combinations k ns = filter ((k==).length) (subsequences ns) <br />
</haskell><br />
<br />
A funny solution using Applicative in Control.Applicative. Funny because it's the opposite of other solutions.<br />
The idea is to generate all possible combinations by allowing permutations and by allowing multiple instances of one value in the list.<br />
Then we filter the list to stick with the exercice.<br />
<haskell><br />
-- let's try it with combinations 2 [1,2,3]<br />
combinations :: (Ord a) => Int -> [a] -> [[a]]<br />
combinations n xs = compressed<br />
where<br />
-- create all combinations (multiple instances, permutations allowed)<br />
-- answer : [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]<br />
combinations' n _ | n <= 0 = [[]]<br />
combinations' 1 xs = map (:[]) xs<br />
combinations' n xs = (:) <$> xs <*> combinations (n-1) xs<br />
-- sort every sublist and the list itself after that<br />
-- [[1,1],[1,2],[1,2],[1,3],[1,3],[2,2],[2,3],[2,3],[3,3]]<br />
sorted = sort . map sort $ combinations' n xs<br />
-- for each sublist, eliminate duplicates (see Problem 8)<br />
-- [[1],[1,2],[1,2],[1,3],[1,3],[2],[2,3],[2,3],[3]]<br />
grouped = map (map head . group) sorted<br />
-- filter all sublist with length < n,<br />
-- this means that they had at least two times the same value in it<br />
-- [[1,2],[1,2],[1,3],[1,3],[2,3],[2,3]]<br />
filtered = filter (\xs -> length xs == n) grouped<br />
-- eliminate duplicates a second time, this time in the list itself<br />
-- [[1,2],[1,3],[2,3]]<br />
compressed = map head . group $ filtered<br />
</haskell><br />
The long list of variables in the where clause are there for educational purpose.</div>Ibizamanhttps://wiki.haskell.org/index.php?title=Talk:99_questions/Solutions/26&diff=43934Talk:99 questions/Solutions/262012-01-14T08:47:00Z<p>Ibizaman: </p>
<hr />
<div>The second solution from the bottom is not correct because it generates also all combinations with k-1, k-2, ..., 0 elements. I didn't check the other solutions.<br />
--[[User:Alexraasch|Alexraasch]] 09:56, 23 September 2011 (UTC)<br />
<br />
I agree totally, (I put it myself), I just put another version of it just now</div>Ibizamanhttps://wiki.haskell.org/index.php?title=99_questions/Solutions/26&diff=4393299 questions/Solutions/262012-01-13T23:55:18Z<p>Ibizaman: added one solution with Applicative</p>
<hr />
<div>(**) Generate the combinations of K distinct objects chosen from the N elements of a list<br />
<br />
In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the<br />
well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.<br />
<br />
<haskell><br />
-- Import the 'tails' function<br />
-- > tails [0,1,2,3]<br />
-- [[0,1,2,3],[1,2,3],[2,3],[3],[]]<br />
import Data.List (tails)<br />
<br />
-- The implementation first checks if there's no more elements to select,<br />
-- if so, there's only one possible combination, the empty one,<br />
-- otherwise we need to select 'n' elements. Since we don't want to<br />
-- select an element twice, and we want to select elements in order, to<br />
-- avoid combinations which only differ in ordering, we skip some<br />
-- unspecified initial elements with 'tails', and select the next element,<br />
-- also recursively selecting the next 'n-1' element from the rest of the<br />
-- tail, finally consing them together<br />
<br />
-- Using list comprehensions<br />
combinations :: Int -> [a] -> [[a]]<br />
combinations 0 _ = [ [] ]<br />
combinations n xs = [ y:ys | y:xs' <- tails xs<br />
, ys <- combinations (n-1) xs']<br />
<br />
-- Alternate syntax, using 'do'-notation <br />
combinations :: Int -> [a] -> [[a]]<br />
combinations 0 _ = return []<br />
combinations n xs = do y:xs' <- tails xs<br />
ys <- combinations (n-1) xs'<br />
return (y:ys)<br />
</haskell><br />
<br />
Another solution that's slightly longer, but doesn't depend on <hask>tails</hask>:<br />
<br />
<haskell><br />
combinations :: Int -> [a] -> [[a]]<br />
-- We don't actually need this base case; it's just here to<br />
-- avoid the warning about non-exhaustive pattern matches<br />
combinations _ [] = [[]]<br />
-- Base case--choosing 0 elements from any list gives an empty list<br />
combinations 0 _ = [[]]<br />
-- Get all combinations that start with x, recursively choosing (k-1) from the<br />
-- remaining xs. After exhausting all the possibilities starting with x, if there<br />
-- are at least k elements in the remaining xs, recursively get combinations of k<br />
-- from the remaining xs.<br />
combinations k (x:xs) = x_start ++ others<br />
where x_start = [ x : rest | rest <- combinations (k-1) xs ]<br />
others = if k <= length xs then combinations k xs else []<br />
</haskell><br />
<br />
Variant: This version avoids getting a result consisting of the empty choice if we ask for, say, 10 elements from the empty list. (Instead, an empty list, suggesting "no options available" is returned.)<br />
<haskell><br />
combinations :: Int -> [a] -> [[a]]<br />
combinations 0 _ = [[]]<br />
combinations _ [] = []<br />
combinations n (x:xs) = (map (x:) (combinations (n-1) xs)) ++ (combinations n xs)<br />
</haskell><br />
<br />
A solution using subsequences in Data.List<br />
<haskell><br />
combinations k ns = filter ((k==).length) (subsequences ns) <br />
</haskell><br />
<br />
A simple solution using Applicative in Control.Applicative<br />
<haskell><br />
combinations :: Int -> [a] -> [[a]]<br />
combinations n _ | n <= 0 = [[]]<br />
combinations 1 xs = map (:[]) xs<br />
combinations n xs = (:) <$> xs <*> combinations (n-1) xs<br />
</haskell></div>Ibizamanhttps://wiki.haskell.org/index.php?title=99_questions/Solutions/22&diff=4393199 questions/Solutions/222012-01-13T23:15:59Z<p>Ibizaman: added one solution with scanl</p>
<hr />
<div>Create a list containing all integers within a given range.<br />
<br />
<haskell><br />
range x y = [x..y]<br />
</haskell><br />
or<br />
<haskell><br />
range = enumFromTo<br />
</haskell><br />
or<br />
<haskell><br />
range x y = take (y-x+1) $ iterate (+1) x<br />
</haskell><br />
or<br />
<haskell><br />
range start stop<br />
| start > stop = reverse (range stop start)<br />
| start == stop = [stop]<br />
| start < stop = start:range (start+1) stop<br />
</haskell><br />
The following does the same but without using a reverse function<br />
<haskell><br />
range :: Int -> Int -> [Int]<br />
range n m<br />
| n == m = [n]<br />
| n < m = n:(range (n+1) m)<br />
| n > m = n:(range (n-1) m)<br />
</haskell><br />
or with scanl<br />
<haskell><br />
range l r = scanl (+) l (replicate (l - r) 1)<br />
</haskell><br />
<br />
Since there's already syntactic sugar for ranges, there's usually no reason to define a function like 'range' in Haskell. In fact, the syntactic sugar is implemented using the enumFromTo function, which is exactly what 'range' should be.</div>Ibizaman