[Haskell-beginners] Haskell triangular loop (correct use of (++))

[AntC]

> rohan sumant <r.s.sumant <at> gmail.com> writes:
>
>  The approach I am following is this :-
> mkpairs [] = []
> 
> mkpairs (x:xs) = (map (fn x) xs) ++ (mkpairs xs)
> fn x y = (x,y)
> 
> It is generating the desired output ...

Good! You've got the right approach for triangular loops.
That is a form

mkpairs (x:xs) = {- stuff -} $ mkpairs xs

A couple of things look non-idiomatic. So before I get on to your main question:

As well as an empty list being a special case,
neither can you make any pairs from a singleton ;-). I suggest:

mkpairs [x] = []

The auxiliary `fn` is messy. I would put explicit lambda:

mkpairs (x:xs) = map (\x' -> (x, x') ) xs ++ mkpairs xs

Or even switch on tuple sections 
https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/
syntax-extns.html#tuple-sections

mkpairs (x:xs) = map (x, ) xs ++ mkpairs xs

> but I am a bit unsure about the time complexity of the function mkpairs. ...
> I am particularly worried about the (++) operator. ...

You are spot-on! (++) has terrible time complexity.
Use the showS trick for constant-time concatenation.
Look in the Prelude for class Show a/method showsPrec,
explained in the Haskell 2010 report section 6.3.3.

To get that to work, you need a 'worker' function
to hand across the successor for each list.
It's conventional to call that `go`,
and because everyone uses `go`,
wrap it inside mkpairs using a `where`.

Complete code:

mkPairs [] = []
mkPairs [x] = []
mkPairs (x:xs) = go xs $ mkPairs xs
  where go [] s = s
             go (x':xs') s = (x, x') : go xs' s

Now is that any faster in practice?
Probably not until you get to a list with thousands of elements.

HTH