Comonadically building Pascal's Triangle

I was reading [1] and one of the comments suggested implementing Pascal's Triangle comonadically as an exercise. However the approach I'm trying to take doesn't work out since I can't find an un-arbitrary implementation for coreturn of T's Even constructor, and I /don't/ want to represent Pascal's Triangle with a 2D grid, as in [1]'s U type.


class Functor w => Comonad w where
    coreturn :: w a -> a
    cojoin   :: w a -> w (w a)
    (=>>)    :: w a -> (w a -> b) -> w b
    x =>> f = fmap f $ cojoin x

data T x = Odd  [x]   x   [x]
         | Even [x] (x,x) [x]

instance Functor T where
    fmap f (Odd  l    m    r) = Odd  (fmap f l)    (f m)     (fmap f r)
    fmap f (Even l (ml,mr) r) = Even (fmap f l) (f ml, f mr) (fmap f r)

instance Comonad T where
    coreturn (Odd  _ m _) = m
    coreturn (Even ? ? ?) = ?

So, what can I do? Is there even a sensible instance of Comonad for the representation I've chosen, or do I just /have/ to use a grid-like structure for the data type?

In joyful anticipation of your illuminating comments, a fellow /prog/rider.

[1] http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html

"Haskell" is a Hebrew name.

I don't see what this has to do with Ruki☆Suta.

Why did you use the Odd and Even representation? You can reuse the U datatype from the article. You just have to change the rule to get your next generation.

>>3
Fuck you and fuck Konata.

fuck type theory

>>5
I would enjoy fucking both myself and Konata.

>>4
I'm quite aware that I could've done this. The reasoning behind using T lies in the fact, that it better fits the shape of Pascal's Triangle, namely a triangular one.

If not sure if this is what you are after, but this implementation takes the current list, appends and prepends ones to it, generates a list of adjacent pairs, and then maps it with apply +.

(2 2) -> (1 2 2 1) -> ((1 2) (2 2) (2 1)) -> (3 4 3)


(define (rev-adj-pairs lis acc)
  (if (or (null? lis) (null? (cdr lis)))
    acc
    (rev-adj-pairs (cdr lis)
                   (cons (list (car lis) (cadr lis))
                         acc))))

(define (adj-pairs lis acc)
  (reverse (rev-adj-pairs lis acc)))

(define (adj-pairs-with-caps first-elem lis last-elem)
  (if (null? lis)
    (list first-elem last-elem)
    (let* ((lis-with-first-elem (cons first-elem lis))
           (rev-adj-pairs-with-first-elem (rev-adj-pairs lis-with-first-elem '()))
           (rev-adj-pairs-with-all (cons (list (cadar rev-adj-pairs-with-first-elem) last-elem) rev-adj-pairs-with-first-elem))
           (adj-pair-all (reverse rev-adj-pairs-with-all)))
      adj-pair-all)))

(define (pascal-next gen)
  (map (lambda (pair) (apply + pair))
       (adj-pairs-with-caps 1 gen 1)))

(define (collect-orbit f x i acc)
  (if (= i 0)
    (reverse acc)
    (let ((v (f x)))
      (collect-orbit f v (- i 1) (cons v acc)))))

(collect-orbit pascal-next '(1) 10 '())

>>8
Imagine each row as an infinite list of numbers, where the numbers "outside" the triangle are zero.

>>9
No, that's not what I'm after.

>>10
Did you even read my question?

>>10
infinite list of numbers
Back to Israel, jewstorm.

I came up with something like this:

firstRow                 = U (repeat 0) 0 (1 : repeat 0)
rule       (U (a:_) b _) = a + b
getPascals (U _ _ rs)    = takeWhile (/= 0) rs

main = mapM_ print $ take 10
     $ map getPascal
     $ iterate (=>> rule) firstRow

If I understand right, though, this is exactly the definition you didn't want. This is the one that makes sense, though: the big mistake you're making is thinking U has a "grid-like" shape, while it's really a "tape" shape, which is really perfect for a single row of Pascal's triangle:

... 0 0 0 0 <0> 1 0 0 0 ...
... 0 0 0 0 <0> 1 1 0 0 ...
... 0 0 0 0 <0> 1 2 1 0 ...
... 0 0 0 0 <0> 1 3 3 1 ...
etc.

In other words: did you even think about >>10's answer?

I'm bumping this because it's a good thread.

Did you even read my question?
No.

>>13
the big mistake you're making is thinking U has a "grid-like" shape, while it's really a "tape" shape, which is really perfect for a single row of Pascal's triangle:
U itself has a tape-like shape, correct. The point though is, that as soon as I'm cojoining U its shape is effectively a 2D-grid.
In other words: did you even think about >>10's answer?
Yes.

>>16
as soon as I'm cojoining U its shape is effectively a 2D-grid

It's more like a pointer to a pointer, or a tape of tapes with each subtape head on a different item, which is what you want when editing a single row:

   U (tape of tapes)
  ...
 ( U ... 0 0 0 0 <0> 1 3 3 1 ... ) (subtape: ls !! 1)
 ( U ... 0 0 0 0 <1> 3 3 1 0 ... ) (subtape: ls !! 0)
<( U ... 0 0 0 1 <3> 3 1 0 0 ... ) (subtape:    x   )>
 ( U ... 0 0 1 3 <3> 1 0 0 0 ... ) (subtape: rs !! 0)
 ( U ... 0 1 3 3 <1> 0 0 0 0 ... ) (subtape: rs !! 1)
  ...

The shape of U (U a) looks like a 2D grid, but it makes more sense to think of it as a tape of tapes, because that's what you're using it as.

Maybe I'm misunderstanding, but I think you're trying to create a T comonad in >>1 so that T (T a) looks like a triangle, but that's impossible, because the shape has to extend infinitely in both dimensions: Pascal's Triangle has infinite rows, but each row is finite.

(This is the best talk I've had on /prog/ in a year or so. Comonads are interesting!)

APL Pascal's triangle:
1,(0,¨⍳¨R)!R←⍳6
(Replace 6 with the number of rows)

>>18
In the time it took you to type those hieroglyphs, I could have implemented an ANSI C compiler in Scheme.

>>18-19
J doesn't require any hieroglyphics, and can do Pascal's triangle in fewer characters:
!/~i.6

>>20
The equivalent APL:
(⍳6)∘.!⍳6
NARS2000 has an extension allowing ∘.!⍨⍳6
This Pascal's triangle is sideways. Does J have a column-major ordering?

>>21                                               `
>mfw APL code is posted
⍨

have you tried symta?

Pascal is shit, why are you still using it

>>21
NARS2000, why the fuck do you even know about it?

>>25
It's better than Java.