Arrays - Inserting and moving data

[Timon Gehr]

On 02/13/2012 03:19 PM, James Miller wrote:
> On 11 February 2012 10:45, Jonathan M Davis<jmdavisProg at gmx.com>  wrote:
>> On Friday, February 10, 2012 13:32:56 Marco Leise wrote:
>>> I know that feeling. I had no exposure to functional programming and
>>> options like chain never come to my head. Although "map" is a concept that
>>> I made friends with early.
>>
>> It would benefit your programming in general to learn a functional programming
>> language and become reasonably proficient in it, even if you don't intend to
>> program in it normally. It'll increase the number of tools in your programming
>> toolbox and improve your programming in other programming languages. It's
>> something that not enough programmers get sufficient exposure to IMHO.
>>
>> - Jonathan M Davis
>
> I found that learning Haskell made me significantly better at what I
> do. New paradigms are good for reminding you to think outside the box,
> I also learnt Prolog for a university course (AI) and that was an
> interesting challenge. Logical programming, where you define the
> boundaries of the program and then it works out the possible answers
> for you, amazingly useful for BNF grammars and similar constructs.
>
> If fact it's got to the point where I feel hamstrung if I can't do at
> least function passing (fortunately C, C++ and D can do this), and I
> prefer to work with languages that support closures and anonymous
> functions, since you can do wonders with simple constructs like map,
> fold (reduce) and filter. In fact a naive implementation of quicksort
> can be done succinctly in any language that supports filter.
>
>      T[] sort(T)(T[] array) {
>          pivot = array[array.length/2];
>          return sort(filter!("a<  "~pivot)(array)~pivot~sort(filter!("a
>> "~pivot)(array));
>      }
>
> (Disclaimer, this is probably a very slow implementation, possibly
> very broken, may cause compiler demons to possess your computer, DO
> NOT USE!)
>
> I have left out some details for brevity, and it probably won't work
> in alot of situations, but it demonstrates the power of functional
> programming, quicksort in 4 lines (sort of, its not like Haskell's
> "quicksort in 2 lines" is any better mind you, its slow as balls
> because of all the memory allocation it has to do).
>
> Anyway, yay for functional programming and thread derailment.
>
> James

If it is slow and uses an awful lot of auxiliary memory it is not 
quicksort as much as it may conceptually resemble quicksort. Try to 
implement in-place quicksort in Haskell. It will look like C code. Also 
see: 
http://stackoverflow.com/questions/5268156/how-do-you-do-an-in-place-quicksort-in-haskell