I'm new to Haskell and have been given a worksheet question which has me stumped. The question is asking me to define a function that takes a list of tuples, each of which contains a sublist of numbers and returns a list of tuples, each of which contains a pair of integers. This is the intended input & output.
possibles [([1],[2,3,4]),([1,2],[3,4])] ===> [(1,234),(1,243),(1,342),(1,324),(1,423),(1,432),(12,34),(12,43),(21,34),(21,43)]
I am attempting to use the “permutations” function from the “Data.List” library and two other functions that I have made and attached below.
-- takes a list of digits and returns the positive integer formed from those digits, so that number [9,1,2,4] ==⇒ 9124
number :: [Int] -> Int
number digits = foldl (\acc x -> acc * 10 x) 0 digits
-- returns all of the non-trivial splits of a list as a list of pairs, so that splits [1,2,3,4,5] ⇒ [([1],[2,3,4]),([1,2],[3,4]),([1,2,3],[4])]
splits :: [Int] -> [([Int], [Int])]
splits [] = []
splits [x] = []
splits (x : xs) = ([x], xs) : map f (splits xs)
where
f (z, y) = (x : z, y)
CodePudding user response：
welcome to the Haskell family! This is an interesting problem that helps you discover the beauty of Haskell.
First, let's look at the problem first, before going into implementation:
- turn
[2,3,4]to[[2,3,4], [2,4,3], [3,2,4], [3,4,2], [4,2,4], [4,3,2]] - turn
[2,3,4]to234(you've implemented this part) - turn
([12,21], [34,43])to[(12,34),(12,43),(21,34),(21,43)] - compose everything together (composition is really powerful)
- refactor
Secondly, here are 2 useful tools I recommend:
- https://replit.com/languages/haskell - online Haskell REPL to test code out quickly
- https://hoogle.haskell.org/ - search Haskell functions that are available, and study the source code if you want to learn the implementation
Now let's try to implement this.
First of all, we know the input type is [([Int], [Int])]:
-- try out at https://replit.com/languages/haskell
input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]
main = print input
Now let's follow the steps mentioned above.
Step 1 is called permutation :: [a] -> [[a]], it doesn't only apply to Int, but to a list of any type.
If you search [a] -> [[a]] in hoogle, you may find this function, now back to the REPL:
import Data.List (permutations)
input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]
step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations
main = print $ step1 [2,3,4]
-- result: [[2,3,4],[3,2,4],[4,3,2],[3,4,2],[4,2,3],[2,4,3]]
For step 2, let's use your code for now:
import Data.List (permutations)
input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]
step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations
step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 x) 0 digits
-- or try the shorter version
-- step2 = foldl (\acc x -> acc * 10 x) 0
main = print $ step2 [2,3,4]
-- result: 234
Step 3 is a good example of using list comprehension:
import Data.List (permutations)
input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]
step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations
step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 x) 0 digits
step3 :: ([a], [b]) -> [(a, b)]
step3 (xs, ys) = [(x,y) | x <- xs, y <- ys]
main = print $ step3 ([12,21], [34,43])
-- result: [(12,34),(12,43),(21,34),(21,43)]
Now the exciting part - composition.
First we combine step1 and step2:
import Data.List (permutations)
input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]
step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations
step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 x) 0 digits
step3 :: ([a], [b]) -> [(a, b)]
step3 (xs, ys) = [(x,y) | x <- xs, y <- ys]
step12 :: [Int] -> [Int]
step12 xs = map step2 (step1 xs)
-- step12 = map step2 . step1
main = print $ step12 [2, 3, 4]
-- result: [234,324,432,342,423,243]
Notice that you can focus on function composition without caring about the value here:
step12 :: [Int] -> [Int]
step12 = map step2 . step1
Now we combine step3 with step12
import Data.List (permutations)
input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]
step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations
step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 x) 0 digits
step3 :: ([a], [b]) -> [(a, b)]
step3 (xs, ys) = [(x,y) | x <- xs, y <- ys]
step12 :: [Int] -> [Int]
step12 xs = map step2 (step1 xs)
-- step12 = map step2 . step1
step123 :: ([Int], [Int]) -> [(Int, Int)]
step123 (xs, ys) = step3 (step12 xs, step12 ys)
main = print $ step123 ([1,2],[3,4])
-- result: [(12,34),(12,43),(21,34),(21,43)]
Now the last step is a simple map or fmap if you will.
Let's see what we've got so far:
import Data.List (permutations)
input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]
step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations
step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 x) 0 digits
step3 :: ([a], [b]) -> [(a, b)]
step3 (xs, ys) = [(x,y) | x <- xs, y <- ys]
step12 :: [Int] -> [Int]
step12 xs = map step2 (step1 xs)
-- step12 = map step2 . step1
step123 :: ([Int], [Int]) -> [(Int, Int)]
step123 (xs, ys) = step3 (step12 xs, step12 ys)
main = print $ map step123 input
-- result: [[(1,234),(1,324),(1,432),(1,342),(1,423),(1,243)],[(12,34),(12,43),(21,34),(21,43)]]
Now we get [[(Int, Int)]] through (map step123 input), all we need to do is a function that turns [[a]] into [a], let's search it in hoogle (be careful to choose the one with the correct behaviour). OK we found concat.
So let's put step4 here to finalise our first version of the solution:
import Data.List (permutations)
input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]
step1 :: [a] -> [[a]]
-- challenge yourself and see if you can implement it
-- feel free to look at the source code for the function in hoogle
step1 = permutations
step2 :: [Int] -> Int
step2 digits = foldl (\acc x -> acc * 10 x) 0 digits
step3 :: ([a], [b]) -> [(a, b)]
step3 (xs, ys) = [(x,y) | x <- xs, y <- ys]
step12 :: [Int] -> [Int]
step12 xs = map step2 (step1 xs)
-- step12 = map step2 . step1
step123 :: ([Int], [Int]) -> [(Int, Int)]
step123 (xs, ys) = step3 (step12 xs, step12 ys)
step4 :: [([Int], [Int])] -> [(Int, Int)]
step4 x = concat (map step123 x)
-- step4 = concat . map step123
-- step4 = concatMap step123
main = print $ step4 input
-- result: [(1,234),(1,324),(1,432),(1,342),(1,423),(1,243),(12,34),(12,43),(21,34),(21,43)]
Note here, again, we can focus on composition without thinking about the value:
step4 :: [([Int], [Int])] -> [(Int, Int)]
step4 = concat . map step123
-- alternatively
-- step4 = concatMap step123
Now let's see how we can refactor step123 with list comprehension and rename it to something like getCombinations:
import Data.List (permutations)
input :: [([Int], [Int])]
input = [([1],[2,3,4]),([1,2],[3,4])]
toNumber :: [Int] -> Int
toNumber = foldl1 (\x y -> 10*x y)
-- ([1, 2], [3, 4]) -> [(12, 34), (12, 43), (21, 34), (21, 43)]
getCombinations :: ([Int], [Int]) -> [(Int, Int)]
getCombinations (xs, ys) = [
(toNumber x, toNumber y)
| x <- permutations xs
, y <- permutations ys]
handleInput :: [([Int], [Int])] -> [(Int, Int)]
handleInput = concatMap getCombinations
main = print . handleInput $ input
This is by no means the most succinct or performant code, but it's a good start and I hope you can learn something out of it.
You're having a great start, keep up the great work and enjoy Haskell :)
CodePudding user response：
We can first simplify the problem to:
possibles :: [([Int], [Int])] -> [(Int, Int)]
possibles = concatMap (uncurry possible')
Since each item in the input is a separate case.
For the possible' it is sufficient to generate all permutations from x and y, and then convert these to a number:
possible' :: [Int] -> [Int] -> [(Int, Int)]
possible' xs ys = [
(x, number ys')
| xs' <- permutations xs
, let x = number xs'
, ys' <- permutations ys
]
It produces results in a different order:
ghci> possibles [([1],[2,3,4]),([1,2],[3,4])]
[(1,234),(1,324),(1,432),(1,342),(1,423),(1,243),(12,34),(12,43),(21,34),(21,43)]
But by implementing a different permutation function, you can alter the order in which items will be generated.
For:
possibles [([1],[2,3,4,5,6,7,8,9]),([1,2],[3,4,5,6,7,8,9]),([1,2,3],[4,5,6,7,8,9]),([1,2,3,4],[5,6,7,8,9]),([1,2,3,4,5],[6,7,8,9]),([1,2,3,4,5,6],[7,8,9]),([1,2,3,4,5,6,7],[8,9]),([1,2,3,4,5,6,7,8],[9])]
This should generate 1!×8! 2!×7! 3!×6! 4!×5! 5!×4! 6!×3! 7!×2! 8!×1! = 2× (1!×8! 2!×7! 3!×6! 4!×5!) = 2× 57'600 = 115'200