Re: [Haskell-cafe] [Template Haskell Question] On defining recursive templates.

20 Jan 2016

      ...
...
Hello Haskellers, > > I'm currently diving into Template Haskell and
I just read the > original TH paper [1]. There they give the following
example of a > generic zip function: > > -- | A generic zip function.
Use (e.g.,) as $(zipN 3) xs ys zs. > zipN :: Int -> ExpQ > zipN n = [|
let zp = $(mkZip n [| zp |]) in zp |] > > -- | Helper function for zipN.
mkZip :: Int -> ExpQ -> ExpQ > mkZip n contZip = lamE pYs (caseE (tupE
eYs) [m1, m2]) >   where >     (pXs, eXs)   = genPEs "x" n >     (pXSs,
eXSs) = genPEs "xs" n >     (pYs, eYs)   = genPEs "y" n >    
allCons      = tupP $ zipWith (\x xs -> [p| $x : $xs |]) pXs pXSs >    
m1           = match allCons continue []     >     m2           = match
wildP stop [] >     continue     = normalB [| $(tupE eXs) : $(appsE
(contZip:eXSs))|] >     stop         = normalB (conE '[]) > > -- |
Generates n pattern and expression variables. > genPEs :: String -> Int
-> ([PatQ], [ExpQ]) > genPEs x n = (pats, exps) >   where names        =
map (\k -> mkName $ x ++ show k) [1..n] >         (pats, exps) = (map
varP names, map varE names) > > This works as expected, e.g., `$(zipN 3)
[1..3] [4..6] [7..9]' gives > [(1,4,7),(2,5,8), (3,6,9)]. > > However, I
found this definition of passing `[| zp |]' as a helper > function
slightly confusing, so I tried to make it more succinct and to > call
zipN directly in the recursion: > > zipN' :: Int -> ExpQ > zipN' n =
lamE pYs (caseE (tupE eYs) [m1, m2]) >   where >     (pXs, eXs)   =
genPEs "x" n >     (pXSs, eXSs) = genPEs "xs" n >     (pYs, eYs)   =
genPEs "y" n >     allCons      = tupP $ zipWith (\x xs -> [p| $x : $xs
|]) pXs pXSs >     m1           = match allCons continue []     >    
m2           = match wildP stop [] >     continue     = normalB [|
$(tupE eXs) : $(appsE (zipN n:eXSs)) |] >     stop         = normalB
(conE '[]) > > This subtle change, however, causes the compiler to
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Its not the compiler diverging, its your own code generating an infinite
expression.

[| zp |] is just a variable capturing the zp from the let expression.
The generated code looks like this:

let zp = \ y1 y2 y3 -> case (y1, y2, y3) of
    ((x1:xs1), (x2:xs2), (x3:xs3)) -> (x1, x2, x3) : zp xs1 xs2 xs3
    _ -> []
    in zp

You on the other hand call zipN from zipN', so the above expression is
inserted instead of zp. And in this expression there is again a zp,
which you replaced... and so on... so it looks like this:

\ y1 y2 y3 -> case (y1, y2, y3) of
    ((x1:xs1), (x2:xs2), (x3:xs3)) -> (x1, x2, x3) :
        (\ y1 y2 y3 -> case (y1, y2, y3) of
            ((x1:xs1), (x2:xs2), (x3:xs3)) -> (x1, x2, x3) :
                (\ y1 y2 y3 -> case (y1, y2, y3) of
                    ((x1:xs1), (x2:xs2), (x3:xs3)) -> (x1, x2, x3) :
(...) xs1 xs2 xs3
                    _ -> []) xs1 xs2 xs3
            _ -> []) xs1 xs2 xs3
    _ -> []

Hopefully it is now clear what is happening ; )

Jonas

On 01/20/2016 08:01 PM, Dominik Bollmann wrote:
diverge and to get > stuck at compiling splice `$(zipN' 3) [1..3] [4..6]
[7..9]'... > > Could anyone explain to me why the first approach works,
but the 2nd > small deviation does not? Is it because the compiler keeps
trying to > inline the recursive call to (zip N) into the template
indefinitely? > > Are there easier (more straightforward) alternative
implementations to > the (imo) slightly convoluted example of zipN from
the paper? > > Any hints are very much appreciated. > > Thanks, >
Dominik. > > [1]
http://research.microsoft.com/~simonpj/papers/meta-haskell/ >
_______________________________________________ > Haskell-Cafe mailing
list > Haskell-Cafe@haskell.org >
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Template Haskell Question] On defining recursive templates.

Jonas Scholl