# Returning items which are different from their preceding items from a list

I have a list of tuples (key, value1, value2, ...). I simplify the tuple here so it is only of length 2. Keys contain duplicated figures.

xs = zip([1,2,2,3,3,3,4,1,1,2,2], range(11)) # simple to input

[(1, 0),
(2, 1),
(2, 2),
(3, 3),
(3, 4),
(3, 5),
(4, 6),
(1, 7),
(1, 8),
(2, 9),
(2, 10)]


Now, I would like to build a function, which takes the list as input, and return a list or generator, which is a subset of the original list.

It must captures all items where the keys are changed, and include the first and last items of the list if they are not already there.

f1(xs) = [(1, 0), (2, 1), (3, 3), (4, 6), (1, 7), (2, 9), (2, 10)]
f1([]) = []


The following is my code, it works, but I don't really like it:

xs = zip([1,2,2,3,3,3,4,1,1,2,2], range(11))

def f1(xs):
if not xs:
return
last_a = None # I wish I don't have to use None here.
is_yield = False
for a, b in xs:
if a != last_a:
last_a = a
is_yield = True
yield (a, b)
else:
is_yield = False
if not is_yield:
yield (a, b) # Ugly...in C# a, b is not defined here.

print list(f1(xs))
print list(f1([]))


What's a better (functional or nonfunctional) way of doing this?

• @Barry I rephased a little bit. My input list is a list of tuples... so on input [(1,a),(2,b),(2,c)] I want [(1,a),(2,b),(2,c)] – colinfang Oct 27 '13 at 23:10
• if you want an answer for specific languages you need to post separate questions with the coding done in those languages. we will not translate this code for you, nor will we write code for you – Malachi Nov 27 '13 at 16:19

The itertools library has a handy function for this problem called groupby:

def f1(xs):
for _, group_iter in itertools.groupby(xs, key = lambda pair: pair[0]):
group = list(group_iter)
yield group[0]


That'll get us the pairs for which the first element changed from the previous one. Now we just need to make sure we're yield-ing the last element. Which will only NOT be yielded if the last group has size more than 1, hence:

def f1(xs):
for _, group_iter in itertools.groupby(xs, key = lambda pair: pair[0]):
group = list(group_iter)
yield group[0]

# make sure we yield xs[-1]
if len(group) > 1:
yield group[-1]

• great, don't know that groupby is not the same as SQL – colinfang Oct 27 '13 at 23:47
• Need group = None and then check if group to handle empty xs. – colinfang Oct 28 '13 at 17:35

For interest value here's a custom recursive solution in F# that performs a pairwise comparison, always keeping the first value, and the last if it wasn't already included.

let pairwiseFilter input =
let rec aux acc = function
| x::y::xs when fst x <> fst y -> aux (y::acc) (y::xs)
| x::y::xs -> aux acc (y::xs)
| x::[] -> List.rev (if x <> acc.Head then x::acc else acc)
| [] -> acc


Note the requirement to always include the first item is handled by simply passing it in as the initial value of the results accumulator. From there we compare the first and second items, and if they are different we add the second item to the results. Then we take the second item and cons it to the rest of the list (pairwise) which is processed recursively.

Finally the resulting list has the last element appended if it wasn't already in the previous step (eg, its not the same as the head of the results accumulator). The results are then reversed to preserve the original input order.

Here's a sloution using Seq.pairwise:

let f input =
let result =
[-1,-1] @ input
|> Seq.pairwise
|> Seq.filter (fun ((key1, valu1), (key2, value2)) -> key1 <> key2)
|> Seq.map snd
|> Seq.toList
if not input.IsEmpty && Seq.last result <> Seq.last input
then result @ [Seq.last input] else result


We add a dummy element to the beginning of the list to make sure it is included, and then at the end cover the last item

>let xs = [1, 0
2, 1
2, 2
3, 3
3, 4
3, 5
4, 6
1, 7
1, 8
2, 9
2, 10]
>f xs
val it : (int * int) list =
[(1, 0); (2, 1); (3, 3); (4, 6); (1, 7); (2, 9); (2, 10)]

>f []
val it : (int * int) list = []