CODEWITHSUNDEEP
haskell
Johanna Larsson
Johanna Larsson

Reputation: 10761

All possible sublists as pairs haskell

Bit unsure on how to phrase this properly, so bear with me!

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

A part B of the question would be to get all possible orderings inside sublists too. So in the case of the first tuple, I'd want the 2 3 4 in the order 243, 324, 432, 423...

Yes, I like non-determinism.

Upvotes: 4

Views: 1363

Answers (4)

MtnViewMark
MtnViewMark

Reputation: 5140

I like Dan's answer best, as I think it is most instructive. However, if you were worrying about the efficiency of splitPair, then I think this rather straight forward definition works fine:

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

This definition differs somewhat from the original problem statement in that it returns pairs where the first or last list is empty. This is more in-line with the definition of most list functions like 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],[])]

Upvotes: 1

Dan Burton
Dan Burton

Reputation: 53665

Part A: Use the non-determinism monad! (the list monad)

Step 1: find an appropriate method for splitting a 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 to work for one index.

splitPair xs = splitAt 1 xs

Step 3: make it work non-deterministically for many indexes.

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

See how easily a single-choice function can be transformed into a non-deterministic-choice function? (This is written just as easily as a list comprehension:)

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

Part B: use the non-determinism monad some more!

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

Further thoughts

The list monad is great for writing simple functions and transforming them into non-deterministic functions. This method, however, is not always the most efficient. In my example, I used operations like length xs and splitAt i xs, which must traverse the length of the list in order to perform their tasks (well, splitAt only needs to traverse through index i, which is on average half the length of the list, so same order of magnitude). Converting to and from a Sequence might be wise if performance is important.

Upvotes: 3

dave4420
dave4420

Reputation: 47052

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 whether 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 former. In that case

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

Final edit: As I've already used a couple of functions from Control.Arrow, I'll note that zip (inits xs) (tails xs) can also be written as (inits &&& tails) xs, but I'm not sure it's clearer that way.

Upvotes: 4

Steves
Steves

Reputation: 3234

In the first case you just need to split the list into two. First one will contain the input and second one will be initially empty. Than take one element by one from the first one, and put it in the second one until the first one is empty.

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

The next question: it is just simple permutation of 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

Upvotes: 2

Related Questions