Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/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: vector indexing time (Heinrich Apfelmus)
2. Re: vector indexing time (Ivan Vyalov)
3. Re: vector indexing time (KC)
4. Why is the the transpose function in Data.List more
complicated? (KC)
5. Re: Why is the the transpose function in Data.List more
complicated? (Greg Fitzgerald)
6. growing trees (Jeff Lasslett)
7. GHC / system libraries (Christopher Howard)
8. growing trees (Jeff Lasslett)
----------------------------------------------------------------------
Message: 1
Date: Fri, 03 Aug 2012 13:50:11 +0200
From: Heinrich Apfelmus <[email protected]>
Subject: Re: [Haskell-beginners] vector indexing time
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
Ivan Vyalov wrote:
> Hi everyone!
>
> I have a question about time complexity of vector indexing.
> Obviously, it should be constant, but if I do the following naive
> tests it looks linear. What do I do wrong?
Creating the vector still takes time proportional to the length of the
vector. In fact, it appears that in your example, the vector packages
optimizes the creation time to create only up to the element that you
actually demand.
The linear time you're seeing is not the result of an inefficiency of
vector indexing, but the result of an efficiency in vector creation.
Best regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 2
Date: Fri, 03 Aug 2012 14:04:43 +0200
From: Ivan Vyalov <[email protected]>
Subject: Re: [Haskell-beginners] vector indexing time
To: Heinrich Apfelmus <[email protected]>,
[email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
On 08/03/2012 01:50 PM, Heinrich Apfelmus wrote:
> Ivan Vyalov wrote:
>> Hi everyone!
>>
>> I have a question about time complexity of vector indexing.
>> Obviously, it should be constant, but if I do the following naive
>> tests it looks linear. What do I do wrong?
>
> Creating the vector still takes time proportional to the length of the
> vector. In fact, it appears that in your example, the vector
> packages optimizes the creation time to create only up to the element
> that you actually demand.
>
> The linear time you're seeing is not the result of an inefficiency of
> vector indexing, but the result of an efficiency in vector creation.
>
>
> Best regards,
> Heinrich Apfelmus
>
> --
> http://apfelmus.nfshost.com
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
Thank you, I've got it. Thanks to other guys who replied to!
Ivan
------------------------------
Message: 3
Date: Fri, 3 Aug 2012 12:21:03 -0700
From: KC <[email protected]>
Subject: Re: [Haskell-beginners] vector indexing time
To: Heinrich Apfelmus <[email protected]>, haskell-cafe
<[email protected]>, [email protected]
Message-ID:
<camlkxymis5kcqr1bx0+axagxga-pdprvbu1w5k0y1qauevt...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Thank you for that insight. :)
On Fri, Aug 3, 2012 at 4:50 AM, Heinrich Apfelmus <[email protected]
> wrote:
>
> Creating the vector still takes time proportional to the length of the
> vector. In fact, it appears that in your example, the vector packages
> optimizes the creation time to create only up to the element that you
> actually demand.
>
> The linear time you're seeing is not the result of an inefficiency of
> vector indexing, but the result of an efficiency in vector creation.
>
>
> Best regards,
> Heinrich Apfelmus
>
> --
> http://apfelmus.nfshost.com
>
>
--
--
Regards,
KC
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120803/652fafa4/attachment-0001.htm>
------------------------------
Message: 4
Date: Fri, 3 Aug 2012 16:34:41 -0700
From: KC <[email protected]>
Subject: [Haskell-beginners] Why is the the transpose function in
Data.List more complicated?
To: haskell-cafe <[email protected]>, [email protected]
Message-ID:
<CAMLKXykO5D+AEx5oSwtLktr_fDaO+Sw9+MRSCs5E=bkm-mh...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Transpose in Data.List is the following:
transpose :: [[a]] -> [[a]]
transpose [] = []
transpose ([] : xss) = transpose xss
transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs :
[ t | (_:t) <- xss])
Yet this seems to work.
transp :: [[b]] -> [[b]]
transp ([]:_) = []
transp rows = map head rows : transp (map tail rows)
Why is the the transpose function in Data.List more complicated?
--
--
Regards,
KC
------------------------------
Message: 5
Date: Fri, 3 Aug 2012 17:05:10 -0700
From: Greg Fitzgerald <[email protected]>
Subject: Re: [Haskell-beginners] Why is the the transpose function in
Data.List more complicated?
To: KC <[email protected]>
Cc: [email protected], haskell-cafe <[email protected]>
Message-ID:
<CAFLa5WMoigh=aP+7h6TZhSGzhjha=rk3u2vn386_h3tkegm...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Hi KC,
> transp :: [[b]] -> [[b]]
> transp ([]:_) = []
> transp rows = map head rows : transp (map tail rows)
>
> Why is the the transpose function in Data.List more complicated?
In the Data.List version, the list comprehension syntax quietly
filters out items that fail to pattern-match (empty lists). Therefore
the transpose in Data.List does not generate a pattern-match exception
when you give it lists of different lengths:
transpose [[1], [], [3]] == [[1,3]]
The Data.List version also returns an empty list if the input is an
empty list, whereas your version returns an infinite list of empty
lists.
-Greg
------------------------------
Message: 6
Date: Sat, 4 Aug 2012 11:21:40 +1000
From: Jeff Lasslett <[email protected]>
Subject: [Haskell-beginners] growing trees
To: [email protected]
Message-ID:
<cak6+hbyufxgxmejwtkmwebvhctppdvfxe9pyonpwhef8ywk...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Greetings,
For my own edification I have written a few functions for creating a
tree from a list of 'associations'.
An association is defined as
data Assoc = Assoc { label :: String
, assocId :: Int
, assocPid :: Int
}
deriving ( Show )
where assocId is an int that uniquely identifies a node, and assocPid
is the id of that node's parent.
The idea is to feed an array of these associations into a function and
get a Data.Tree Assoc out.
So I have code that does the job ... ... but it's not very good. I
thought the problem might be
solved with a fold, but that proved difficult due to the Assocs not
being in a suitable insertion order.
Perhaps the routines can be improved such that the array order doesn't matter.
Any advice, or better versions would be appreciated.
thanks,
Jeff
PS: AssocTree.hs should be attached.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: AssocTree.hs
Type: application/octet-stream
Size: 2670 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120804/685324ca/attachment-0001.obj>
------------------------------
Message: 7
Date: Fri, 03 Aug 2012 21:04:15 -0800
From: Christopher Howard <[email protected]>
Subject: [Haskell-beginners] GHC / system libraries
To: Haskell Beginners <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
I know that GHC allows you to create shared libraries and create
binaries that use shared libraries, because I asked that question some
time ago on this list. However, I was wondering: can the GHC "standard
libraries" be decoupled from the compiler? I.e., so you can install the
libraries and the binaries on a system without the compiler being installed?
I use a source-based distro so it is of little relevance to me. However,
I was discussing Haskell apps online with some friends who use
binary-based distros and had to admit that I wasn't clear on this point.
--
frigidcode.com
indicium.us
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 554 bytes
Desc: OpenPGP digital signature
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120803/12a56223/attachment-0001.pgp>
------------------------------
Message: 8
Date: Sat, 4 Aug 2012 15:07:51 +1000
From: Jeff Lasslett <[email protected]>
Subject: [Haskell-beginners] growing trees
To: beginners <[email protected]>
Message-ID:
<cak6+hbxdwkptmafg5+ghqpi7fazpsbkam05brxr7rwvez6b...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Hello again,
There were a few details I accidentally omitted from my initial email.
I've attached my code again.
As I mentioned in my first message on this subject, I'm just after
some guidance on ways to improve upon what I've written. How can I
make it clearer, more concise??
Here's a transcript of a ghci session showing how I generate a tree
from a list of associations:
*AssocTree> let related = filterUnrelated assocs
*AssocTree> let t = growTree ( Node r [] ) related
*AssocTree> printTree t
root
|
+- C
| |
| +- f
| |
| +- e
| | |
| | `- m
| |
| `- D
| |
| +- g
| | |
| | +- i
| | |
| | `- j
| | |
| | `- k
| |
| `- h
|
+- B
|
`- A
-------------- next part --------------
A non-text attachment was scrubbed...
Name: AssocTree.hs
Type: application/octet-stream
Size: 2670 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120804/08ad1cfb/attachment.obj>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 50, Issue 5
****************************************
