title: SKI transform, how to program in a functional language
body: <p>I am facing the following Prolog code. The expression [X]>>Y stands
  for the lambda expression lambda X.Y. The code eliminates the lambda
  and gives a combinatory expression over S, K and I:</p>
  
  <pre><code>convert([X]&gt;&gt;Y,'I') :- X==Y, !.
  convert([X]&gt;&gt;Y,apply('K',Y)) :- var(Y), !.
  convert([X]&gt;&gt;([Y]&gt;&gt;Z),R) :-
       convert([Y]&gt;&gt;Z,H), convert([X]&gt;&gt;H,R).
  convert([X]&gt;&gt;apply(Y,Z),apply(apply('S',S),T)) :-
       convert([X]&gt;&gt;Y,S), convert([X]&gt;&gt;Z,T).
  convert([_]&gt;&gt;Y,apply('K',Y)).
  </code></pre>
  
  <p>Here is an example how it works:</p>
  
  <pre><code> ?- convert([X]&gt;&gt;([Y]&gt;&gt;apply(Y,X)),R).
   R = apply(apply('S', apply(apply('S', apply('K', 'S')), 
    apply('K', 'I'))), apply(apply('S', apply('K', 'K')), 'I'))
  </code></pre>
  
  <p>Suppose I would like to code the same <strong>conversion</strong> in Haskell, ML, or 
  the like. How can I do this? Can I use the lambda expressions available
  in the functional programming language directly? Or do I have to 
  regress to some meta programming facilities?</p>
  
  <p>Best Regards</p>
  
  <p>P.S.: The code above is not the SKI conversion that leads to very short
  SKI expressions. Better code is possible that checks for occurence of
  the bound variable in the lambda expression body.</p>