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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Семен Тригубенко http://trygub.com