Stack Overflow
Stack Overflow

Questions tagged [scott-encoding]

Scott encoding is a way to represent data through functions. It differs from the Church encoding in its treatment of recursive data types.

Scott encoding is a way to represent (recursive) data types in the lambda calculus.

See also: Mogensen-Scott encoding on Wikipedia.

9 questions
16
votes
2 answers

Why do we use folds to encode datatypes as functions?

Or to be specific, why do we use foldr to encode lists and iteration to encode numbers? Sorry for the longwinded introduction, but I don't really know how to name the things I want to ask about so I'll need to give some exposition first. This draws…
hugomg
  • 68,213
  • 24
  • 160
  • 246
13
votes
3 answers

More efficient tail of church encoded list

This is a literate haskell post. Simply save it as "ChurchList.lhs" to run it. > {-# LANGUAGE Rank2Types #-} A Church encoded list is a way of representing a list via a function. It resembles both folding and continuation passing style. > newtype…
PyRulez
  • 10,513
  • 10
  • 42
  • 87
10
votes
2 answers

Why are explicit forall quantifiers necessary for rank-n types?

When I declare this newtype: newtype ListScott a = ListScott { unconsScott :: (a -> ListScott a -> r) -> r -> r } which would define the hypothetical rank-2 type ListScott :: ((a -> ListScott a -> r) -> r -> r) -> ListScott a, the compiler…
user6445533
10
votes
4 answers

How do I use the Church encoding for Free Monads?

I've been using the Free datatype in Control.Monad.Free from the free package. Now I'm trying to convert it to use F in Control.Monad.Free.Church but can't figure out how to map the functions. For example, a simple pattern matching function using…
Anupam Jain
  • 7,851
  • 2
  • 39
  • 74
5
votes
2 answers

How to infer the type of the Scott encoded List constructor?

Scott encoded lists can be defined as followed: newtype List a = List { uncons :: forall r. r -> (a -> List a -> r) -> r } As opposed to the ADT version List is both type and data constructor. Scott encoding determines ADTs through…
user5536315
5
votes
1 answer

Is there any non-recursive term that folds over a scott-encoded list?

Suppose that I have a scott-encoded list such as: scott = (\ c n -> c 1 (\ c n -> c 2 (\ c n -> c 3 (\ c n -> n)))) I want a function that receives such kind of list and converts it to an actual list ([1,2,3]), except that such function can not be…
MaiaVictor
  • 51,090
  • 44
  • 144
  • 286
3
votes
2 answers

How do you represent nested types using the Scott Encoding?

An ADT can be represented using the Scott Encoding by replacing products by tuples and sums by matchers. For example: data List a = Cons a (List a) | Nil Can be encoded using the Scott Encoding as: cons = (λ h t c n . c h t) nil = (λ c n . n) But…
MaiaVictor
  • 51,090
  • 44
  • 144
  • 286
1
vote
1 answer

How to use a Reader type encoded with continuation passing style

I was under the impression that every value of type a can be described with a rank-2 polymorphic type newtype Id a = Id {runId :: forall r. (a -> r) -> r } in continuation passing style. So I derived the following type to define the Reader…
user6445533
0
votes
1 answer

How to implement Haskell's newtype using a function encoding?

Heads-up: This is a cross-language question. I will demonstrate the problem by means of implementing a difference list. Here is the Scott encoded List, which provides the basic type. I use it with a dynamic type validator, hence I need a wrapper to…
user5536315