How to double iterator in FP style: pairing list into (n, n + k)

Learn
16

I hate making assumptions about the validity of input data. Especially input in Lists (which are not sets, and are not guaranteed ascending): really it’s a shame there are so many beginners’ exercise using only Lists; Haskell is no longer Lisp with bells on; early in an intro you should be introduced to more appropriate data structures (Data.Set would be my go-to here).

However, I’ve assumed for the exercise:

  • the input list is not necessarily ascending;
  • it is not necessarily a set (duplicate elements allowed);
  • it is not necessarily possible to pair up all the elements exhaustively

See the deviant tests.

inList = [1, 3, 4, 6, 7, 10, 12, 15]

rawPairs k xs@(_: ys@(_:_)) = [(x, y) | x <- xs, y <- ys, x+k == y]

filterDups _ [] = []
filterDups xy@(_,y) xys@(xy'@(x',_): xys')
               | y == x'    = filterTail
--             | y <  x'    = xys               -- optimisation, assumes ascending
               | otherwise  = xy' : filterTail
           where filterTail = filterDups xy xys'


nonDupPairs k xs = go $ rawPairs k xs
    where go []         = []
          go (xy : xys) = xy : go (filterDups xy xys)


{-  -- tests
nonDupPairs 3 inList
===> [(1,4),(3,6),(7,10),(12,15)]

nonDupPairs 3 [1,4,7]
===> [(1,4)]

nonDupPairs 3 [4,1,4,7]
===> [(4,7),(1,4)]

nonDupPairs 3 [4,1]
===> []
nonDupPairs 3 [7,4,1]
===> [(1,4)]

nonDupPairs 3 [1,5,8,10,14]
===> [(5,8)]
nonDupPairs 3 [1,5,6,7,8,11,15]
===> [(5,8)]
nonDupPairs 3 [1,5,9,10,14]
===> []

-}

The test with [4,1] produces nothing, because of the y <- ys optimisation in the List comprehension. Changing that to y <- xs, as @jaror’s List comprehension, does then yield [(1,4)].