rohan sumant
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