[Haskell-cafe] Q about last&init
Semen Trygubenko / Семен Тригубенко
semen at trygub.com
Thu Jul 17 12:57:02 UTC 2014
On Thu, Jul 17, 2014 at 01:35:58PM +0400, Закиров Марат wrote:
> I am teaching myself haskell. The first impression is very good.
> But phrase "haskell is polynomially reducible" is making me sad :(.
Cheer up my friend.
You know what makes _me_ sad?
250+ soldiers, fine Ukrainian men in their prime, dead; 1000+ wounded. In two months...
> Anyway I am trying to backport my algorithm written in C. The key to
> performance is to have ability to remove element from the end of a
> list in O(1).
> But the original haskell functions last and init are O(n).
> My questions are:
> 1) Is last function is something like "black box" written in C++ which
> perform O(1)?
> So I shouldn't even try to imagine some haskell O(1) equivalent.
> 2) Or will optimizer (llvm?) reduce init&last complexity to 1?
> 3) Some people suggest to use sequences package, but still how do they
> implement O(1) init&last sequences equivalent in haskell?
> Regards, Marat.
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
Семен Тригубенко http://trygub.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 196 bytes
Desc: not available
More information about the Haskell-Cafe