lambdaway :: perm3

5 | list | login |load

| |

_h1 [[perm2]] | perm3

_p The goal is to display the list of permutations of the elements of some list.

{prewrap
'{L.disp
 {L.permut
  {L.new 1 2}}}
-> {L.disp {L.permut {L.new 1 2}}}

'{L.disp
 {L.permut
  {L.new 1 2 3}}} 
-> {L.disp {L.permut {L.new 1 2 3}}}

'{L.disp
 {permut
  {L.new A T C G}}}  // 24 permutations
-> {L.disp {L.permut {L.new A T C G}}}

'{L.disp
 {L.permut
  {L.new {L.new Belle marquise}
         {L.new vos beaux yeux} 
         {L.new me font mourir} 
         {L.new d'amour}}}}
-> {L.disp
   {L.permut
    {L.new {L.new Belle marquise}
           {L.new vos beaux yeux} 
           {L.new me font mourir} 
           {L.new d'amour}}}} 
}

_p where

{pre
'{def L.permut
 {lambda {:a}
  {if {L.empty? :a}
   then {L.new :a}
   else {let { {:c {{lambda {:a :b} {L.inject {L.first :a} :b}} :a}}
               {:d {L.permut {L.rest :a}}}
             } {L.reduce L.concat {L.map :c :d}}}}}}
-> {def L.permut
 {lambda {:a}
  {if {L.empty? :a}
   then {L.new :a}
   else {let { {:c {{lambda {:a :b} {L.inject {L.first :a} :b}} :a}}
               {:d {L.permut {L.rest :a}}}
             } {L.reduce L.concat {L.map :c :d}}}}}}

'{def L.inject
 {lambda {:x :a}
  {if {L.empty? :a}
   then {L.new {L.new :x}}  
   else {let { {:c {{lambda {:a :b} {L.concat {L.new {L.first :a}} :b}} :a}}
               {:d {L.inject :x {L.rest :a}}}
               {:e {L.concat {L.new :x} :a}}
             } {L.concat {L.new :e} {L.map :c :d}}}}}} 
-> {def L.inject
 {lambda {:x :a}
  {if {L.empty? :a}
   then {L.new {L.new :x}}  
   else {let { {:c {{lambda {:a :b} {L.concat {L.new {L.first :a}} :b}} :a}}
               {:d {L.inject :x {L.rest :a}}}
               {:e {L.concat {L.new :x} :a}}
             } {L.concat {L.new :e} {L.map :c :d}}}}}}
}

_p Lambdatalk comes with sets of primitives dealing with {b W}ords, {b S}entences, {b A}rrays and {b P}airs, but not with {b lists}. Lists are a special type of PAIRS, the left element is a word and the right one is a list or some terminal element choosen to be {b nil}. Lists elements can also be lists. Concerning pairs {b P.new} builds a pair from two words, {b P.pair?} tests if a word is a pair or not, and {b P.left & P.right} gets the left and right terms. concerning sentences, {b S.empy?} tests if a sentence is empty and {b S.first & S.rest} gets the first term and the rest of the sentence.

_p The {b L.permut & L.inject} functions are built using the following functions

{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}}}}}}

'{def L.first
 {lambda {:l}
  {P.left :l}}}
-> {def L.first {lambda {:l} {P.left :l}}}

'{def L.rest
 {lambda {:l}
  {P.right :l}}}
-> {def L.rest {lambda {:l} {P.right :l}}}

'{def L.empty?
 {lambda {:l}
  {not {P.pair? :l}}}}
-> {def L.empty? {lambda {:l} {not {P.pair? :l}}}}

'{def L.disp
 {def L.disp.r
  {lambda {:l}
   {if {L.empty? :l}
    then .
    else {if {P.pair? {L.first :l}}
          then {L.disp {L.first :l}}
          else {L.first :l}}
         {L.disp.r {L.rest :l}}}}}
 {lambda {:l}
  {S.replace \s\. by in ({L.disp.r :l})}}}
-> {def L.disp
 {def L.disp.r
  {lambda {:l}
   {if {L.empty? :l}
    then .
    else {if {P.pair? {L.first :l}}
          then {L.disp {L.first :l}}
          else {L.first :l}}
         {L.disp.r {L.rest :l}}}}}
 {lambda {:l}
  {S.replace \s\. by in ({L.disp.r :l})}}}
}

_p Examples

{pre
'{def L {L.new a b c}}
-> {def L {L.new a b c}}

'{L.empty? {L}}
-> {L.empty? {L}}
'{L.empty? nil}
-> {L.empty? nil}

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

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

'{L.disp {L.new {L.new a b c} {L.new d e f}}}
-> {L.disp {L.new {L.new a b c} {L.new d e f}}}

'{L.disp
 {L.new
  {L.new a {L.new 1 2 3} c}
  {L.new d {L.new 4 5 6} f}}}
-> {L.disp
 {L.new
  {L.new a {L.new 1 2 3} c}
  {L.new d {L.new 4 5 6} f}}}
}

_p Some more functions required here

{pre
'{def L.concat
 {lambda {:l1 :l2}
  {if {L.empty? :l1}
   then :l2
   else {P.new {L.first :l1} {L.concat {L.rest :l1} :l2}}}}}
-> {def L.concat
 {lambda {:l1 :l2}
  {if {L.empty? :l1}
   then :l2
   else {P.new {L.first :l1} {L.concat {L.rest :l1} :l2}}}}}

'{def L.map
 {lambda {:f :l}
  {if {L.empty? :l}
   then nil
   else {P.new {:f {L.first :l}} {L.map :f {L.rest :l}}}}}}
-> {def L.map
 {lambda {:f :l}
  {if {L.empty? :l}
   then nil
   else {P.new {:f {L.first :l}} {L.map :f {L.rest :l}}}}}}

'{def L.reduce
 {lambda {:f :l}
  {if {L.empty? :l}
   then nil
   else {:f {L.first :l} {L.reduce :f {L.rest :l}}}}}}
-> {def L.reduce
 {lambda {:f :l}
  {if {L.empty? :l}
   then nil
   else {:f {L.first :l} {L.reduce :f {L.rest :l}}}}}}
}

_p Examples

{pre
'{L.disp
 {L.map sqrt {L.new 1 2 3 4}}}
-> {L.disp {L.map sqrt {L.new 1 2 3 4}}}

'{L.disp
 {L.concat
  {L.new a b c}
  {L.new d e f}}}
-> {L.disp {L.concat {L.new a b c} {L.new d e f}}}

'{L.disp
 {L.reduce
  L.concat
   {L.new {L.new 1 2 3}
          {L.new 3 4 5}
          {L.new 6 7 8}}}}
-> {L.disp {L.reduce L.concat {L.new {L.new 1 2 3} {L.new 3 4 5} {L.new 6 7 8}}}}
}

_p {i alain marty 2022/06/08}