All possible signatures as haskell pairs

Question

I don’t know how to formulate it correctly, so bear with me!

Given a list of [1,2,3,4], I want a list of tuples of lists, for example: [([1], [2,3,4]), ([1,2], [3,4]), ( [1,2,3], [4])].

Part B of the question will be to get all possible ordering within the subscriptions. Therefore, in the case of the first tuple, I would like 2 3 4 in the order of 243, 324, 432, 423 ...

Yes, I like determinism.

Answer 1

import Data.List (inits, tails, permutations) import Control.Arrow (first, second) parta :: [a] -> [([a], [a])] parta [] = [] parta xs = init . tail $ zip (inits xs) (tails xs) 

For part b, I'm not sure if you want [([1],[2,3,4]), ([1],[3,4,2]), ...] or [([1],[[2,3,4],[3,4,2],...]), ...] . If the latter, then

 partb :: [a] -> [([a], [[a]])] partb = map (second permutations) . parta 

Edit: Oh, but you want the first one. In this case

 partb :: [a] -> [([a], [a])] partb = map (uncurry zip . first repeat . second permutations) . parta 

Final editing: since I already used several functions from Control.Arrow, I noticed that zip (inits xs) (tails xs) can also be written as (inits &&& tails) xs , but I'm not sure if this is clear that way .

Answer 2

Part A: Use monads without determinism! (list monad)

Step 1 : find a suitable method for splitting the list into a tuple of two lists.

Hoogling [a] -> ([a], [a]) we find splitAt :: Int -> [a] -> ([a],[a])

 import Data.List (splitAt, permutations) -- we'll need to permute for part B 

Step 2 : write it down to work with a single index.

 splitPair xs = splitAt 1 xs 

Step 3 : make it non-deterministic for many indices.

 splitPairs xs = do index <- [1..length xs-1] return $ splitAt index xs 

See how easily one selection function can be transformed into a function without deterministic selection? (This is written as easy as list comprehension :)

 splitPairs' xs = [splitAt i xs | i <- [1..length xs-1]] 

Part B: use monads without determinism a little more!

 splitPairsPerms xs = do (ys, zs) <- splitPairs xs ys' <- permutations ys zs' <- permutations zs return $ (ys', zs') 

Further thoughts

List monad is great for writing simple functions and converting them to non-deterministic functions. However, this method is not always the most effective. In my example, I used operations such as length xs and splitAt i xs , which must cross the length of the list to perform their tasks (well, splitAt needs to go through the index i, which is on average half the length of the list, the same order of magnitude). Converting to and from a sequence may be reasonable if performance is important.

Answer 3

In the first case, you just need to split the list into two. The first will contain the input, and the second will be initially empty. Then take one element one from the first and place it in the second until the first becomes empty.

 magic x = magic' x [] where magic' [] y = [[[], y]] magic' (x:xs) y = [[reverse y, (x:xs)]] ++ magic' xs (x:y) 

The next question: this is just a permutation of the elements.

 perm x = perm' x [] [] where perm' [] [] prefix = [prefix] perm' [] rest prefix = [] perm' (x:xs) rest prefix = perm' (xs++rest) [] (x:prefix) ++ perm' xs (x:rest) prefix 

Answer 4

I like Dan to respond better, as I think it is instructive. However, if you were worried about the effectiveness of splitPair , then I think this pretty direct definition works fine:

 splitPair :: [a] -> [([a],[a])] splitPair [] = ([],[]) : [] splitPair a@ (x:xs) = ([],a) : map (\(u,v)->(x:u,v)) (splitPair xs) 

This definition is somewhat different from the original problem statement in that it returns pairs where the first or last list is empty. This is more consistent with the definition of most list functions, such as tails or inits :

 > splitPair [1,2,3,4] [([],[1,2,3,4]),([1],[2,3,4]),([1,2],[3,4]),([1,2,3],[4]),([1,2,3,4],[])]