title: Pattern matching on deque
body: <p>I'm trying to do some pattern matching on deque in haskell, but have some problems. </p>
  
  <p>Here is some explanation for what i'm trying to do.</p>
  
  <p>I'm trying to implement a compiler from Refal to Haskell. Refal is a language that uses pattern matching alot. So a typical refal function looks like this:</p>
  
  <pre><code>    RefalFunc {
           e.1 s.1 (e.2) 's' t.1 t.2 t.1 e.2 = e.1 e.2
           e.1 ' ' e.2 = 'foo' e.1 'foo' e.2
           e.1 = 'anyexpression'
      }
  </code></pre>
  
  <p>So this function takes an refal-expression (which consists of terms) and try to match it with 1 of 3 patterns, and if it succeeded then transform refal-expression into another according to rules on the right side.</p>
  
  <p>e.1, e.2 .. - means some refal-expressions
  t.1 t.2 - means some terms , for example "(e.1 t.2 e.2)" is a term, "e.1 t.2 e.2" is not 
  s.A s.1   - means symbols
  's' - means symbol 's'. there are some others type of symbols, but it doesn't matter.</p>
  
  <p>In my compiler refal-expressions represent as deques, so for each refal function i need to generate a function, which takes some deque and transform it, according to some pattern. 
  So i have something like this</p>
  
  <pre><code>    myFunc1:: Deque -&gt; Deque
      myFunc1 deq = if matchPattern1 deq then doSomeWork1
                    else if matchPattern2 deq then doSomeWork2
                    ...
                 where matchPattern1 = ...
                       matchPattern2 = ...
                       ....
  </code></pre>
  
  <p>So, the main problem is, that I'm realy don't know how to do that matchPattern functions. </p>
  
  <p>So, for given deque I can easily find first(or last) term or symbol, but i'm don't know what to do, when i meet e.1, which means part of the deque with uknown size. </p>
  
  <p>So here's example.
  Deque: ( 5 + 6 ) * 7 * ( 5 + ( 4 + 1 ) ) * ( 5 + 6 ) * ( 5 + 6 ) //every symbol here is an element of the deque, every non-Bracket symbol is a term, every (/<em>some symbols</em>/) is a term</p>
  
  <p>I need to check is this deque match the following patterns (and find an appropriate partition)</p>
  
  <pre><code> pattern1: t.1 e.1 t.1
   pattern2: t.1 '*' e.1 (t.2 e.2) s.1 t.1 e.3 
  </code></pre>
  
  <p>answer for pattern1 : </p>
  
  <pre><code> t.1 = ( 5 + 6 )
   e.1 =  * 7 * ( 5 + ( 4 + 1 ) ) * ( 5 + 6 ) *
  </code></pre>
  
  <p>answer for pattern2 : </p>
  
  <pre><code> t.1 =  ( 5 + 6 )
   e.1 = 7 *
   t.2 = 5
   s.1 = *
   e.2 = + ( 4 + 1 )  
   e.3 =  * ( 5 + 6 )
  </code></pre>
  
  <p>I'm using an implementation of Okasaki CatenableDeque.</p>