Code golf: Pascal triangle
92 views
Skip to first unread message
Ivan Tarasov
Jan 6, 2012, 8:24:28 PM1/6/12
to baha...@googlegroups.com
After skimming through this (admittedly boring) Hacker News thread, I thought of what would be a nice way to implement Pascal's triangle in Haskell.
An obvious solution is to use zipWith, unfortunately you also need to pad the lists with zeros, and it's quite ugly. The most elegant (and quite short) solution that I've come up with is this:
iterate (foldl' (\(p:ps) v -> (v:(p+v):ps)) [0]) [1]
Can someone suggest a nicer solution?
Ivan
An obvious solution is to use zipWith, unfortunately you also need to pad the lists with zeros, and it's quite ugly. The most elegant (and quite short) solution that I've come up with is this:
iterate (foldl' (\(p:ps) v -> (v:(p+v):ps)) [0]) [1]
Can someone suggest a nicer solution?
Ivan
Mark Lentczner
Jan 9, 2012, 12:16:45 AM1/9/12
to baha...@googlegroups.com
Not sure why the zipWith version needs to be ugly:
iterate (\f -> zipWith (+) f (0:f) ++ [1]) [1]
Compressing space, it ends up being the smallest of these:
iterate(\f->zipWith(+)f(0:f)++[1])[1]iterate((++[1]).((0:)>>=zipWith(+)))[1]iterate(foldr(\v(p:q)->v:(p+v):q)[0])[1]
That is, assuming we are going for maximum golf!
Ivan Tarasov
Jan 9, 2012, 3:31:43 AM1/9/12
to baha...@googlegroups.com
Mark,
Somehow the 0: and ++[1] combination didn't strike me as nice, that's why I started looking for a different solution. My was a tad longer, but it didn't have that not-so-nice part, and I still hope that someone can find a nicer solution.
Ivan
Somehow the 0: and ++[1] combination didn't strike me as nice, that's why I started looking for a different solution. My was a tad longer, but it didn't have that not-so-nice part, and I still hope that someone can find a nicer solution.
Ivan
--
You received this message because you are subscribed to the Google Groups "Bay Area Haskell Users Group" group.
To view this discussion on the web visit https://groups.google.com/d/msg/bahaskell/-/ZXJtlg_4UqMJ.
To post to this group, send email to baha...@googlegroups.com.
To unsubscribe from this group, send email to bahaskell+...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/bahaskell?hl=en.
Shachaf Ben-Kiki
Jan 9, 2012, 3:37:12 AM1/9/12
to baha...@googlegroups.com
On Mon, Jan 9, 2012 at 00:31, Ivan Tarasov <ivan.t...@gmail.com> wrote:
> Mark,
>
> Somehow the 0: and ++[1] combination didn't strike me as nice, that's why I
> started looking for a different solution. My was a tad longer, but it didn't
> have that not-so-nice part, and I still hope that someone can find a nicer
> solution.
>
> Ivan
>
> Mark,
>
> Somehow the 0: and ++[1] combination didn't strike me as nice, that's why I
> started looking for a different solution. My was a tad longer, but it didn't
> have that not-so-nice part, and I still hope that someone can find a nicer
> solution.
>
> Ivan
>
If it's the asymmetry that you don't like, there's always: iterate (\f
-> zipWith (+) ([0] ++ f) (f ++ [0])) [1]
Shachaf
Ivan Tarasov
Jan 9, 2012, 3:40:57 AM1/9/12
to baha...@googlegroups.com
I guess I just don't like ++'ing lists.
Shachaf Ben-Kiki
Jan 9, 2012, 3:55:27 AM1/9/12
to baha...@googlegroups.com
On Mon, Jan 9, 2012 at 00:40, Ivan Tarasov <ivan.t...@gmail.com> wrote:
> I guess I just don't like ++'ing lists.
>
>
> I guess I just don't like ++'ing lists.
>
>
I agree -- appending to the end of a list isn't as nice as your fold.
Shachaf
Reply all
Reply to author
Forward
0 new messages