View mode: basic / threaded / horizontal-split · Log in · Help
February 10, 2012
Re: Arrays - Inserting and moving data
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
February 13, 2012
Re: Arrays - Inserting and moving data
On 11 February 2012 10:45, Jonathan M Davis <jmdavisProg@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
February 13, 2012
Re: Arrays - Inserting and moving data
On 02/13/2012 03:19 PM, James Miller wrote:
> On 11 February 2012 10:45, Jonathan M Davis<jmdavisProg@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
February 13, 2012
Re: Arrays - Inserting and moving data
On 14 February 2012 06:25, Timon Gehr <timon.gehr@gmx.ch> wrote:
> On 02/13/2012 03:19 PM, James Miller wrote:
>>
>> On 11 February 2012 10:45, Jonathan M Davis<jmdavisProg@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
>

It is still conceptually quicksort, the divide-and-conquer method
based on partitioning the list. I wasn't writing it to show a valid
implementation (I didn't even test it, it probably doesn't compile), I
even warned of compiler demons! Its a demonstration of the
succinctness of functional techniques for certain problems, not a show
that functional languages "are teh awesum and all other langauges
suck". Haskell is almost a pure functional language, therefore, under
normal circumstances, every change to the array will allocate a new
array, this is because of the whole immutability thing that it has
going on. Of course I would never use such an implementation in real
life, and Haskellers tend to avoid algorithms that do these kinds of
things, using sorts like mergesort instead.

Saying "it is not quicksort as much as it may conceptually resemble
quicksort" is kinda odd, its like saying "it is not a car, as much as
it may conceptually resemble a car" because it doesn't run on petrol
or gas, but instead runs on environment destroying orphan tears.

James Miller
February 13, 2012
Re: Arrays - Inserting and moving data
On 02/13/2012 03:34 PM, James Miller wrote:

> Saying "it is not quicksort as much as it may conceptually resemble
> quicksort" is kinda odd, its like saying "it is not a car, as much as
> it may conceptually resemble a car" because it doesn't run on petrol
> or gas, but instead runs on environment destroying orphan tears.

For what its worth, Andrei uses that argument in his "On Iteration" 
article with "For starters, [one implementation of Haskell's] qsort is 
not really quicksort. Quicksort, as defined by Hoare in his seminal 
paper [8], is an in-place algorithm."

  http://www.informit.com/articles/printerfriendly.aspx?p=1407357

Ali
February 14, 2012
Re: Arrays - Inserting and moving data
On 14 February 2012 12:45, Ali Çehreli <acehreli@yahoo.com> wrote:
> On 02/13/2012 03:34 PM, James Miller wrote:
>
>> Saying "it is not quicksort as much as it may conceptually resemble
>> quicksort" is kinda odd, its like saying "it is not a car, as much as
>> it may conceptually resemble a car" because it doesn't run on petrol
>> or gas, but instead runs on environment destroying orphan tears.
>
> For what its worth, Andrei uses that argument in his "On Iteration" article
> with "For starters, [one implementation of Haskell's] qsort is not really
> quicksort. Quicksort, as defined by Hoare in his seminal paper [8], is an
> in-place algorithm."
>
>  http://www.informit.com/articles/printerfriendly.aspx?p=1407357
>
> Ali
>

Fair enough, I didn't realise that Quicksort was defined as in place,
in that case, I retract my opposition to "not really a quicksort"
however my "missing the point" still stands. I still prefer arrays
over S-lists anyway, how else do I efficiently implement a heap?
February 14, 2012
Re: Arrays - Inserting and moving data
On Tuesday, February 14, 2012 13:02:43 James Miller wrote:
> On 14 February 2012 12:45, Ali Çehreli <acehreli@yahoo.com> wrote:
> > On 02/13/2012 03:34 PM, James Miller wrote:
> >> Saying "it is not quicksort as much as it may conceptually resemble
> >> quicksort" is kinda odd, its like saying "it is not a car, as much as
> >> it may conceptually resemble a car" because it doesn't run on petrol
> >> or gas, but instead runs on environment destroying orphan tears.
> > 
> > For what its worth, Andrei uses that argument in his "On Iteration"
> > article with "For starters, [one implementation of Haskell's] qsort is
> > not really quicksort. Quicksort, as defined by Hoare in his seminal
> > paper [8], is an in-place algorithm."
> > 
> > http://www.informit.com/articles/printerfriendly.aspx?p=1407357
> > 
> > Ali
> 
> Fair enough, I didn't realise that Quicksort was defined as in place,
> in that case, I retract my opposition to "not really a quicksort"
> however my "missing the point" still stands. I still prefer arrays
> over S-lists anyway, how else do I efficiently implement a heap?

Orphan tears. It's the only way to go.

- Jonathan M Davis
February 14, 2012
Re: Arrays - Inserting and moving data
On 02/14/2012 12:34 AM, James Miller wrote:
> On 14 February 2012 06:25, Timon Gehr<timon.gehr@gmx.ch>  wrote:
>> On 02/13/2012 03:19 PM, James Miller wrote:
>>>
>>> On 11 February 2012 10:45, Jonathan M Davis<jmdavisProg@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
>>
>
> It is still conceptually quicksort, the divide-and-conquer method
> based on partitioning the list.

Hoare's original quicksort algorithm is more detailed than what is 
sketched here. The main point is the in-place partition operation with 
the two pointers approaching each other.

> I wasn't writing it to show a valid
> implementation (I didn't even test it, it probably doesn't compile), I
> even warned of compiler demons! Its a demonstration of the
> succinctness of functional techniques for certain problems, not a show
> that functional languages "are teh awesum and all other langauges
> suck".

The approach given does not solve the problem (it does not implement 
Quicksort). Quicksort in Haskell looks like Quicksort in D, because the 
algorithm depends on destructive updates. Functional techniques can be 
succinct for certain problems, but implementing Quicksort is not one of 
them.

> Haskell is almost a pure functional language, therefore, under
> normal circumstances, every change to the array will allocate a new
> array,

Haskell can do destructive array updates that look like pure operations 
just fine. 
http://hackage.haskell.org/packages/archive/array/0.2.0.0/doc/html/Data-Array-MArray.html

> this is because of the whole immutability thing that it has going on.

This is confusing the abstraction with its implementation. It is 
impossible to recreate Haskell's execution semantics in D using only 
immutable types.

> Of course I would never use such an implementation in real
> life, and Haskellers tend to avoid algorithms that do these kinds of
> things, using sorts like mergesort instead.
>

Mostly lazy mergesort if I'm not mistaken. And they don't usually use it 
to sort arrays, they sort lists. Haskell arrays ought to be sorted with 
introsort if the comparison operation is cheap.

> Saying "it is not quicksort as much as it may conceptually resemble
> quicksort" is kinda odd, its like saying "it is not a car, as much as
> it may conceptually resemble a car" because it doesn't run on petrol
> or gas, but instead runs on environment destroying orphan tears.
>

It is more like saying "a handcart is not a car, as much as it may 
conceptually resemble a car" (the engine is missing!).
February 15, 2012
Re: Arrays - Inserting and moving data
MattCodr wrote:

> I have a doubt about the best way to insert and move (not 
> replace) some data on an array.

I have the vision, that a mapping from a dense range of integers to 
some value type and wast (i.e. Theta( n)) changes of this mapping are a 
severe hint for a maldesign.

-manfred
Next ›   Last »
1 2
Top | Discussion index | About this forum | D home