At 3:36 AM -0600 10/5/10, Luke Palmer wrote:

On Mon, Oct 4, 2010 at 9:04 PM, Dean Herington wrote:

...

With respect to "datatype destructing" functions, the Prelude has:

maybe :: b -> (a -> b) -> Maybe a -> b either :: (a -> c) -> (b -> c) -> Either a b -> c

which suggests the following signatures for the analogues for Bool and list types:

bool :: a -> a -> Bool -> a list :: b -> (a -> [a] -> b) -> [a] -> b

This suggestion is not so clear to me. Maybe and Either are both non-recursive, so the Church and Scott encodings coincide. You've written the Scott encoding of list. The Church encoding should look familiar:

list :: b -> (a -> b -> b) -> [a] -> b

Intuitively, a Scott encoding peels off one layer of datatype, whereas a Church encoding flattens down a whole recursive structure. Church encodings are more powerful -- you can do more without requiring a fixed point operator.

Just to be clear, I am not arguing anything other than "maybe" and "either" don't readily generalize to "list" because of list's recursiveness.

Luke

Thanks, Luke, for pointing out the Church vs. Scott encoding issue. I agree with your conclusion (and feel better about the lack of the version of "list" I had suggested). Dean