CODEWITHSUNDEEP
haskell
therk12
therk12

Reputation: 41

All non-duplicate combinations of two list elements

It's easier to explain this with an example:

I want to write a function [a] -> [(a,a)] so if I get a list 

[A, B, C, D]

I want this list to return: 

[(A, A), (A,B), (A,C), (A,D), (B,B), (B,C), (B,D), (C,C), (C,D), (D,D)]

I came up with this code: 

function s = [(x,y) | x <- s, y <- s, x<=y]

Which works correctly for a list of integers, but I want this to work for data types that are not instances of the Ord class. My data type derives Show and Eq. So is there a simple way to solve this problem? I'm thinking maybe by filtering the tuples from 

function s = [(x,y) | x <- s, y <- s]

But I dont know how I can do that either.

Upvotes: 4

Views: 185

Answers (4)

ƛƛƛ
ƛƛƛ

Reputation: 892

It's a nested loop.

import Data.List (dropWhile)

com xs = do
  x <- xs
  y <- dropWhile (/= x) xs
  return (x, y)

Upvotes: 2

Elmex80s
Elmex80s

Reputation: 3504

Solution using recursion:

f :: [a] -> [(a, a)]
f []     = []
f (x:xs) = [(x, y) | y <- (x:xs)] ++ f xs

Without recursion: 

import Data.List (tails) 

f' :: [a] -> [(a, a)]
f' xs = concat [[(head x, y) | y <- x] | x <- tails xs]

Without list comprehension:

import Data.List (tails) 

f'' :: [a] -> [(a, a)]
f'' xs = concatMap (\sl -> zip (repeat $ head sl) sl) (tails xs)

Best is by Daniel Wagner, just use

[(head x, y) | x <- tails xs, y <- x]

Upvotes: 4

radrow
radrow

Reputation: 7139

You may use scanr

f l = zip l (scanr (:) [] l) >>= \(h,t) -> fmap ((,) h) t

First you get list of (heads, tails) of l, map tails pairing their elements with corresponding head and finally flatten everything.

Upvotes: 1

jneira
jneira

Reputation: 944

Continuing the idea of filter [(x,y) | x <- xs, y <- xs], you could do it using foldl instead:

f = foldl add [] 
  where add ys (a,b) | notElem (b,a) ys = (a,b):ys 
                     | otherwise = ys

g xs = [(x,y) | x <- xs, y <- xs]

function = f . g

Upvotes: 0

Related Questions