[Haskell-cafe] Q about last&init

[Закиров Марат]

Thank you all guys, really your answers were helpful,

Also I noticed than most of haskell people is in faaaar west from Moscow.

Lisp queue are really cool, thanks Richard (something like that were
been cooking in my head).

I do think that imperative languages are horrible they are unreadable
(they are just "sugar" version of Turing machine :) ).
They constrain SW parallelism with pointer aliasing.
Thay are need to be executed on CPU with retirement buffer.
So my preferences is on functional side...
The big question is all about: how to make code which has ~same
performance in single core CPU with algorithms which are not too much
complex.

But lets speak about problem.

I need to form array of local mins observe.
Radius = 1
In [1, 2, 0, 3, 5, 7, 4] Out [1, 0, 0, 0, 3, 4, 4]
A itself a bit complicated and spaghetti like in my C version.
But verbally it sounds like:
I dynamically form (or support or provide) o sequence of indices's of
strictly increasing elems.
To perform that I push in head new elem just after I have poped all
stuff which is bigger or equal.
Also I remove from the tail all elems that have range bigger than
Radius. And than I just put elem to out array.
Pretty simple huh?

This is a part of bigger procedure (which is image filtration) which
operates on matrix and calculate local mins and maxs by reusing of
described above algorithm in a pretty straightforward way and obtains
O(n) complexity.

--Marat


2014-07-18 10:04 GMT+04:00 Tony Morris <tmorris at tmorris.net>:
> data SnocList a = SnocList ([a] -> [a])
>
> Inserts to the front and end in O(1).
>
> On 17/07/2014 7:47 PM, "Закиров Марат" <marat61 at gmail.com> wrote:
>>
>> Thanks, but maybe I badly formulated my question. I'd like to insert
>> at the beginning of the list and remove from the tail both in O(1).
>>
>>
>> 2014-07-17 13:39 GMT+04:00 Frerich Raabe <raabe at froglogic.com>:
>> > On 2014-07-17 11:35, Закиров Марат wrote:
>> >>
>> >> I am teaching myself haskell. The first impression is very good.
>> >> But phrase "haskell is polynomially reducible" is making me sad :(.
>> >> 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).
>> >
>> >
>> > On viable option might be to adjust the algorithm such that instead of
>> > appending to the list, it prepends (which is O(1) in Haskell), i.e.
>> > you manage the list in reverse and only actually reverse it to the
>> > original order when needed (e.g. when printing).
>> >
>> > --
>> > Frerich Raabe - raabe at froglogic.com
>> > www.froglogic.com - Multi-Platform GUI Testing
>> > _______________________________________________
>> > Haskell-Cafe mailing list
>> > Haskell-Cafe at haskell.org
>> > http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>>
>>
>> --
>> Regards, Marat.
>> С уважением Марат.
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe



-- 
Regards, Marat.
С уважением Марат.