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

[atomly]

https://wiki.haskell.org/99_questions/Solutions/26

:: atomly ::

[ atomly at atomly.com : www.atomly.com  : http://blog.atomly.com/ ...
[ atomiq records : new york city : +1.347.692.8661 ...
[ e-mail atomly-news-subscribe at atomly.com for atomly info and updates ...

On Sun, Apr 10, 2016 at 11:59 AM, rohan sumant <r.s.sumant at gmail.com> wrote:

> Suppose I have a list of distinct integers and I wish to generate all
> possible unordered pairs (a,b) where a/=b.
>
> Ex: [1,2,3,0] --> [(1,2),(1,3),(1,0),(2,3),(2,0),(3,0)]
>
>  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 but I am a bit unsure about the time
> complexity of the function mkpairs. In an imperative language a nested
> triangular for loop would do the trick in O(n^2) or more precisely
> (n*(n-1)/2) operations. Does my code follow the same strategy? I am
> particularly worried about the (++) operator. I think that (++) wouldn't
> add to the time complexity since the initial code fragment (map (fn x) xs)
> is to be computed anyway. Am I wrong here? Is this implementation running
> O(n^2)? If not, could you please show me how to write a nested triangular
> loop in Haskell?
>
> Rohan Sumant
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160414/a4313c63/attachment.html>