Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Haskell triangular loop (correct use of (++)) (atomly)
----------------------------------------------------------------------
Message: 1
Date: Thu, 14 Apr 2016 17:31:18 -0500
From: atomly <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Haskell triangular loop (correct use
of (++))
Message-ID:
<caa_y42yqipcuo6m0g-hu2nuhlkwvked59q67bztvkunsolq...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
https://wiki.haskell.org/99_questions/Solutions/26
:: atomly ::
[ [email protected] : www.atomly.com : http://blog.atomly.com/ ...
[ atomiq records : new york city : +1.347.692.8661 ...
[ e-mail [email protected] for atomly info and updates ...
On Sun, Apr 10, 2016 at 11:59 AM, rohan sumant <[email protected]> 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
> [email protected]
> 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-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 94, Issue 12
*****************************************
