lambdaway :: string

4 | list | login |load

| |

_h1 [[sort]] by string length

_p See [[http://rosettacode.org/wiki/Compare_length_of_two_strings|http://rosettacode.org/wiki/Compare_length_of_two_strings]].

;; _h2 list version

_p Lambdatalk comes with primitives working on {b W}ords, [{b W.equal?, W.length, ...}], on {b S}entences, [{b S.empty?, S.first, S.rest, ...}] and {b P}airs, [{b P.new, P.left, P.right, ...}].

_p Using these primitives we define 2 helper functions, [{b L.new, L.disp}], to build and display a list according to a chosen format.

_h3 L.new

{pre
'{def L.new
 {lambda {:s}
  {if {S.empty? {S.rest :s}}
   then {P.new {S.first :s} nil}
   else {P.new {S.first :s} {L.new {S.rest :s}}}}}}
-> {def L.new
 {lambda {:s}
  {if {S.empty? {S.rest :s}}
   then {P.new {S.first :s} nil}
   else {P.new {S.first :s} {L.new {S.rest :s}}}}}}

'{L.new abcd 123456789 abcdef 1234567}
-> {L.new abcd 123456789 abcdef 1234567}
}

_p Given a sequence of words, {b :s}, we create a new pair made of its first term and the rest of the sequence, until it is empty, the last term being apaired with any terminal word, for instance {b nil}.

_h3 L.disp

{pre
'{def L.disp
 {lambda {:l}
  {if {not {P.pair? :l}} 
   then 
   else {br} {W.length {P.left :l}} : {P.left :l}
        {L.disp {P.right :l}}}}}
-> {def L.disp
 {lambda {:l}
  {if {not {P.pair? :l}}
   then  
   else {br} {W.length {P.left :l}} : {P.left :l}
        {L.disp {P.right :l}}}}}

'{def L {L.new abcd 123456789 abcdef 1234567}}
-> {def L {L.new abcd 123456789 abcdef 1234567}}

'{L.disp {L}}
-> {L.disp {L}}
}

_p Given a list, {b :l} - which is a pair - we extract its left term, display it preceded by its length, and do it again on the right term.

_h3 L.sort

_p Then we define the {b L.sort} function waiting for a predicate function and a list. The algorithm is illustrated in the example below:

{center
{pre

[abcd 123456789 abcdef 1234567]  []
[123456789 abcdef 1234567]   [abcd]
[abcdef 1234567]   [abcd 123456789]
[1234567]   [abcd abcdef 123456789]
[]  [abcd abcdef 1234567 123456789]
}}

_p At each stage the first term in the left-hand list is taken and inserted in its correct place in the right-hand list.

{pre
'{def L.sort
 {lambda {:filter :l} 
  {if {W.equal? :l nil} 
   then nil 
   else {L.insert {P.left :l}
                  :filter
                  {L.sort :filter 
                          {P.right :l}}}}}}
-> {def L.sort
 {lambda {:filter :l} 
  {if {W.equal? :l nil} 
   then nil 
   else {L.insert {P.left :l} :filter
                  {L.sort :filter {P.right :l}}}}}}
}

_h3 L.insert

{pre
'{def L.insert
 {lambda {:x :filter :l} 
  {if {W.equal? :l nil} 
   then {P.new :x nil} 
   else {if {:filter :x {P.left :l}} 
   then {P.new :x :l} 
   else {P.new {P.left :l}
               {L.insert :x
                         :filter 
                         {P.right :l}}}}}}}
-> {def L.insert
 {lambda {:x :filter :l} 
  {if {W.equal? :l nil} 
   then {P.new :x nil} 
   else {if {:filter :x {P.left :l}} 
   then {P.new :x :l} 
   else {P.new {P.left :l}
              {L.insert :x :filter {P.right :l}}}}}}}
}

_h3 filter

_p Using the following predicate function (which could be anonymous) testing the length of 2 words

{pre
'{def filter
 {lambda {:a :b}
  {> {W.length :a} {W.length :b}}}}
-> {def filter {lambda {:a :b} {> {W.length :a} {W.length :b}}}}
}

_p we display the {b B} list sorted according to the length of its elements.

{pre
'{L.disp {L.sort filter {L}}}
-> {L.disp {L.sort filter {L}}}
}

_p {i alain marty| 2022/06/02}

°°°

_h2 array version

{prewrap 
'{def A {A.new abcd 123456789 abcdef 1234567}}
-> {def A {A.new abcd 123456789 abcdef 1234567}}

'{sort {A}}
-> {sort {A}}

'{disp {sort {A}}}
-> {disp {sort {A}}}
}

_p with

{pre
'{def sort

{def sort.insert
  {lambda {:x :a}
   {if {A.empty? :a}
    then {A.new :x}
    else {if {> {W.length :x} {W.length {A.first :a}}}
    then {A.addfirst! :x :a}
    else {A.addfirst! {A.first :a} 
                      {sort.insert :x {A.rest :a}}} }}}}

{def sort.recurse
  {lambda {:a1 :a2}
   {if {A.empty? :a1}
    then :a2 
    else {sort.recurse {A.rest :a1}
                       {sort.insert {A.first :a1} :a2}} }}}

{lambda {:a}
  {sort.recurse :a {A.new}} }}
-> {def sort

{def sort.recurse
  {lambda {:a1 :a2}
   {if {A.empty? :a1}
    then :a2 
    else {sort.recurse {A.rest :a1}
                       {sort.insert {A.first :a1} :a2}} }}}

{lambda {:a}
  {sort.recurse :a {A.new}} }}
}

_p and

{pre
'{def disp
 {lambda {:a}
  {if {A.empty? :a}
   then 
   else {br}{W.length {A.first :a}} : {A.first :a}
        {disp {A.rest :a}}}}}
-> {def disp
 {lambda {:a}
  {if {A.empty? :a}
   then 
   else {br}{W.length {A.first :a}} : {A.first :a}
        {disp {A.rest :a}}}}}
}

°°°