Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Using a concept from Category Theory to enable you to come
back home after your function has taken you somewhere
(Costello, Roger L.)
2. Re: Using a concept from Category Theory to enable you to
come back home after your function has taken you somewhere
(Miguel Negrao)
3. Re: Using a concept from Category Theory to enable you to
come back home after your function has taken you somewhere
(Costello, Roger L.)
4. Re: DPH installation and LLVM ([email protected])
----------------------------------------------------------------------
Message: 1
Date: Sat, 4 Aug 2012 16:43:54 +0000
From: "Costello, Roger L." <[email protected]>
Subject: [Haskell-beginners] Using a concept from Category Theory to
enable you to come back home after your function has taken you
somewhere
To: "[email protected]" <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="us-ascii"
Hi Folks,
When I go hiking, I want to be able to retrace my steps and get back to my
starting point.
When I go to a store, I want to be able to return home.
When I swim out from the shore, I want to be able to get back to the shore.
Going somewhere and then coming back to where one started is important in life.
And it is important in mathematics.
And it is important in functional programming.
If a function maps a set of elements (the domain) to a set of values (the
codomain) then it is often useful to have another function that can take the
elements in the codomain and send them back to their original domain values.
The latter is called the inverse function.
In order for a function to have an inverse function, it must possess two
important properties, which I explain now.
Let the domain be the set of days of the week. In Haskell one can create the
set using a data type definition such as this:
data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
Let the codomain be the set of breakfasts. One can create this set using a data
type definition such as this:
data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits |
Sausage
Now I create a function that maps each element of the domain to a value in the
codomain.
Here is one such function. The first line is the function signature and the
following lines is the function definition:
f :: Day -> Breakfast
f Monday = Eggs
f Tuesday = Cereal
f Wednesday = Toast
f Thursday = Oatmeal
f Friday = Pastry
f Saturday = Ham
f Sunday = Grits
An important thing to observe about the function is that no two elements in the
domain map to the same codomain value. This function is called an injective
function.
[Definition] An injective function is one such that no two elements in the
domain map to the same value in the codomain.
Contrast with the following function, where two elements from the domain --
Monday and Tuesday -- both map to the same codomain value -- Eggs.
g :: Day -> Breakfast
g Monday = Eggs
g Tuesday = Eggs
g Wednesday = Toast
g Thursday = Oatmeal
g Friday = Pastry
g Saturday = Ham
g Sunday = Grits
The function is not injective.
Can you see a problem with creating an inverse function for g :: Day ->
Breakfast?
Specifically, what would an inverse function do with Eggs? Map it to Monday? Or
map it to Tuesday? That is a problem.
[Important] If a function does not have the injective property then it cannot
have an inverse function.
In other words, I can't find my way back home.
There is a second property that a function must possess in order for it to have
an inverse function. I explain that next.
Did you notice in the codomain that there are 8 values:
data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits |
Sausage
So there are more values in the codomain than in the domain.
In function f :: Day -> Breakfast there is no domain element that mapped to
the codomain value Sausage.
So what would an inverse function do with Sausage? Map it to Monday? Tuesday?
What?
The function is not surjective.
[Definition] A surjective function is one such that for each element in the
codomain there is at least one element in the domain that maps to it.
[Important] If a function does not have the surjective property, then it does
not have an inverse function.
[Important] In order for a function to have an inverse function, it must be
both injective and surjective.
One final piece of terminology: a function that is both injective and
surjective is said to be bijective. So, in order for a function to have an
inverse function, it must be bijective.
Recap: if you want to be able to come back home after your function has taken
you somewhere, then design your function to possess the properties of
injectivity and surjectivity.
/Roger
------------------------------
Message: 2
Date: Sat, 4 Aug 2012 18:48:54 +0100
From: Miguel Negrao <[email protected]>
Subject: Re: [Haskell-beginners] Using a concept from Category Theory
to enable you to come back home after your function has taken
you
somewhere
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252
A 04/08/2012, ?s 17:43, Costello, Roger L. escreveu:
>
> [Important] In order for a function to have an inverse function, it must be
> both injective and surjective.
>
> One final piece of terminology: a function that is both injective and
> surjective is said to be bijective. So, in order for a function to have an
> inverse function, it must be bijective.
>
> Recap: if you want to be able to come back home after your function has taken
> you somewhere, then design your function to possess the properties of
> injectivity and surjectivity.
>
> /Roger
Hi Roger,
I learned that a function has an inverse (from it?s image) if and only if it is
injective in high school, don?t think category theory is needed here... But I
have sometimes wondered: a) How do you know that a Haskell function is
injective ? I don?t think it?s possible to write a function which checks if
another function is injective or not . b) How to automatically get the inverse
of a Haskell function ? I think I?ve only seen this done automatically for
functions that are explicitly constructed out of operations which are know to
compose into still injective functions. Can you say something else about this ?
best,
Miguel Negr?o
------------------------------
Message: 3
Date: Sat, 4 Aug 2012 17:59:59 +0000
From: "Costello, Roger L." <[email protected]>
Subject: Re: [Haskell-beginners] Using a concept from Category Theory
to enable you to come back home after your function has taken
you
somewhere
To: "[email protected]" <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="us-ascii"
Hi Miguel,
First note that I am very much a beginner at Category Theory. I am just sharing
what I learn.
> How do you know that a Haskell function is injective? I don't think it's
> possible to write a function which checks if another function is injective or
> not .
A function is injective if each input value (domain) yields a different output
value (codomain). So if the set of inputs is finite, then it should be possible
to write a function that loops over each input value and checks that its output
is distinct from all other outputs.
> How to automatically get the inverse of a Haskell function?
That's a great question. I don't know the answer to that. Anyone else have an
idea?
/Roger
------------------------------
Message: 4
Date: Sat, 4 Aug 2012 17:05:19 -0400
From: [email protected]
Subject: Re: [Haskell-beginners] DPH installation and LLVM
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="windows-1252"
Since I haven't gotten any further answers I'm trying my luck again?
Does anyone have an idea how I can get the llvm backend to work? My
configuration is:
Mac OS X 10.7.4
XCode 4.3.3 (with Command Line Tools installed)
Haskell Platform 2012.2.0.0 32 bit
llvm (via Homebrew)
Oliver
>> Probably the official package from llvm.org unless you use something like
>> macports or homebrew. They should install under /usr/local.
>
> So I went with homebrew which I think installs everything under /usr/local by
> default. Now I get:
>
> ---
> Configuring dph-examples-0.6.1.3...
>
> /var/folders/57/rjs423s5227dnc8rh_2rp4jh0000gn/T/95011.c:1:0:
> internal compiler error: Illegal instruction: 4
> Please submit a full bug report,
> with preprocessed source if appropriate.
> See <URL:http://developer.apple.com/bugreporter> for instructions.
> cabal: Error: some packages failed to install:
> dph-examples-0.6.1.3 failed during the configure step. The exception was:
> ExitFailure 1
> ---
>
> What's wrong?
>
> Oliver
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120804/47280113/attachment-0001.htm>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 50, Issue 6
****************************************
