[Haskell-cafe] Q about last&init

[Semen Trygubenko / Семен Тригубенко]

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...

http://www.pravda.com.ua/news/2014/07/15/7031993/

Anyway.


> 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://www.haskell.org/mailman/listinfo/haskell-cafe

-- 
Семен Тригубенко http://trygub.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140717/0ab3513e/attachment.sig>