1
$\begingroup$

I have read the implementation of QuickSort algorithm in WL from Roman Maeder's Computer Science with Mathematica (2000).

The implementation is shown below.

SetAttributes[swap, {HoldFirst}]
swap[l_, i_, j_] := ({l[[i]], l[[j]]} = {l[[j]], l[[i]]}; l);

SetAttributes[QSort, HoldFirst]
QuickSort[list_] := Module[{l = list}, QSort[l, 1, Length[l]]; l];
QSort[l_, n0_, n1_] /; n0 >= n1 := l;
QSort[l_, n0_, n1_] := 
 Module[{lm = l[[Floor[(n0 + n1)/2]]], i = n0, j = n1},
  While[ True, 
   While[l[[i]] < lm, i++];
   While[l[[j]] > lm, j--];
   If[i >= j, Break[]];
   swap[l, i, j];
   i++; j--];
  QSort[l , n0, i - 1];
  QSort[l, j + 1, n1]
  ]

My question is why should we use HoldFirst? Is it because we are modifying the argument l and this is not allowed in the WL?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Try implementing this without the HoldFirst attribute and see what happens. You get error messages because 'l' evaluates to a list of numbers, and you can't use a Part assignment with a list, only with a symbol. (The error messages link you to the documentation page - the blue icon at the right.) The held argument remains a symbol so the remaining code can function as desired. The default behavior unheld behavior is "smart pass by value", so you are essentially making a copy and modifying parts of the copy. $\endgroup$
    – user87932
    Commented Sep 30, 2023 at 16:46
  • $\begingroup$ Many thanks! Much appreciated. $\endgroup$
    – LambdaHaskell
    Commented Sep 30, 2023 at 19:46
  • $\begingroup$ You're welcome. I should've said that trying to use Set (=) with a list is where the problem lies; Part doesn't care. $\endgroup$
    – user87932
    Commented Oct 1, 2023 at 0:55
  • 1
    $\begingroup$ To answer the last question, yes, it is exactly so l can be modified in place. This is implicit in the remarks already made but should be stated explicitly. Effectively the Hold* attributes, used in this way, provide a "call-by-reference" capability. $\endgroup$
    – Daniel Lichtblau
    Commented Oct 1, 2023 at 18:30
  • $\begingroup$ Thank you is much. Much appreciated. $\endgroup$
    – LambdaHaskell
    Commented Oct 1, 2023 at 18:31

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.