[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://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>

More information about the Haskell-Cafe mailing list