Mark partial functions as such

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
30 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Mark partial functions as such

Richard Eisenberg-4
Proposal: Mark partial functions in `base` as partial

Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.

I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.

Thoughts?

Thanks,
Richard
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Daniel Cartwright
+1, I've always thought it should be like this

On Thu, Aug 30, 2018, 8:10 PM Richard Eisenberg <[hidden email]> wrote:
Proposal: Mark partial functions in `base` as partial

Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.

I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.

Thoughts?

Thanks,
Richard
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Richard Eisenberg-4
In reply to this post by Richard Eisenberg-4
Just to clarify here: all I mean is that we should include the word "Partial" in the Haddock documentation -- no deprecation or warning, just documentation.

Richard

> On Aug 30, 2018, at 8:10 PM, Richard Eisenberg <[hidden email]> wrote:
>
> Proposal: Mark partial functions in `base` as partial
>
> Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.
>
> I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.
>
> Thoughts?
>
> Thanks,
> Richard
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Daniel Cartwright
That's fine, still a +1 from me

On Thu, Aug 30, 2018, 8:13 PM Richard Eisenberg <[hidden email]> wrote:
Just to clarify here: all I mean is that we should include the word "Partial" in the Haddock documentation -- no deprecation or warning, just documentation.

Richard

> On Aug 30, 2018, at 8:10 PM, Richard Eisenberg <[hidden email]> wrote:
>
> Proposal: Mark partial functions in `base` as partial
>
> Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.
>
> I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.
>
> Thoughts?
>
> Thanks,
> Richard
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Daniel Díaz Casanueva
In reply to this post by Richard Eisenberg-4
+1 from me too. The partiality of a function seems to me like something that should be documented.

Best,
Daniel

Am Fr., 31. Aug. 2018 um 02:10 Uhr schrieb Richard Eisenberg <[hidden email]>:
Proposal: Mark partial functions in `base` as partial

Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.

I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.

Thoughts?

Thanks,
Richard
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

David Feuer
Yes, I think so. What about functions like length? length (repeat ()) is bottom. repeat () is not bottom. Ergo, length is partial. But I don't think we want to say that!

On Thu, Aug 30, 2018, 10:05 PM Daniel Díaz Casanueva <[hidden email]> wrote:
+1 from me too. The partiality of a function seems to me like something that should be documented.

Best,
Daniel

Am Fr., 31. Aug. 2018 um 02:10 Uhr schrieb Richard Eisenberg <[hidden email]>:
Proposal: Mark partial functions in `base` as partial

Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.

I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.

Thoughts?

Thanks,
Richard
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Daniel Díaz Casanueva
Why not? I don't think mentioning that length doesn't work with infinite lists will do any harm.

I think many people make a distinction between partiality due to endless evaluation and partiality due to a call to "error". But I still think documenting either of both things can be helpful.

Best,
Daniel

Am Fr., 31. Aug. 2018 um 04:09 Uhr schrieb David Feuer <[hidden email]>:
Yes, I think so. What about functions like length? length (repeat ()) is bottom. repeat () is not bottom. Ergo, length is partial. But I don't think we want to say that!

On Thu, Aug 30, 2018, 10:05 PM Daniel Díaz Casanueva <[hidden email]> wrote:
+1 from me too. The partiality of a function seems to me like something that should be documented.

Best,
Daniel

Am Fr., 31. Aug. 2018 um 02:10 Uhr schrieb Richard Eisenberg <[hidden email]>:
Proposal: Mark partial functions in `base` as partial

Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.

I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.

Thoughts?

Thanks,
Richard
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Eric Mertens
I think this comes down to just documenting things like how strict functions are and how they behave on various classes of inputs. These are good things to document. It doesn’t just have to be about a boolean flag “partial” paste on a bunch of definitions.

On Aug 30, 2018, at 7:16 PM, Daniel Díaz Casanueva <[hidden email]> wrote:

Why not? I don't think mentioning that length doesn't work with infinite lists will do any harm.

I think many people make a distinction between partiality due to endless evaluation and partiality due to a call to "error". But I still think documenting either of both things can be helpful.

Best,
Daniel

Am Fr., 31. Aug. 2018 um 04:09 Uhr schrieb David Feuer <[hidden email]>:
Yes, I think so. What about functions like length? length (repeat ()) is bottom. repeat () is not bottom. Ergo, length is partial. But I don't think we want to say that!

On Thu, Aug 30, 2018, 10:05 PM Daniel Díaz Casanueva <[hidden email]> wrote:
+1 from me too. The partiality of a function seems to me like something that should be documented.

Best,
Daniel

Am Fr., 31. Aug. 2018 um 02:10 Uhr schrieb Richard Eisenberg <[hidden email]>:
Proposal: Mark partial functions in `base` as partial

Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.

I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.

Thoughts?

Thanks,
Richard
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

David Feuer
Yup! Just wanted to make sure it didn't end up being the latter.

On Thu, Aug 30, 2018, 10:19 PM Eric Mertens <[hidden email]> wrote:
I think this comes down to just documenting things like how strict functions are and how they behave on various classes of inputs. These are good things to document. It doesn’t just have to be about a boolean flag “partial” paste on a bunch of definitions.

On Aug 30, 2018, at 7:16 PM, Daniel Díaz Casanueva <[hidden email]> wrote:

Why not? I don't think mentioning that length doesn't work with infinite lists will do any harm.

I think many people make a distinction between partiality due to endless evaluation and partiality due to a call to "error". But I still think documenting either of both things can be helpful.

Best,
Daniel

Am Fr., 31. Aug. 2018 um 04:09 Uhr schrieb David Feuer <[hidden email]>:
Yes, I think so. What about functions like length? length (repeat ()) is bottom. repeat () is not bottom. Ergo, length is partial. But I don't think we want to say that!

On Thu, Aug 30, 2018, 10:05 PM Daniel Díaz Casanueva <[hidden email]> wrote:
+1 from me too. The partiality of a function seems to me like something that should be documented.

Best,
Daniel

Am Fr., 31. Aug. 2018 um 02:10 Uhr schrieb Richard Eisenberg <[hidden email]>:
Proposal: Mark partial functions in `base` as partial

Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.

I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.

Thoughts?

Thanks,
Richard
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Frerich Raabe
In reply to this post by David Feuer
Hi David,

On 2018-08-31 04:09, David Feuer wrote:
> What about functions like length? length (repeat ()) is bottom. repeat () is
> not bottom. Ergo, length is partial.

This caught me by surprise - I would have never considered 'length' to be a
partial function! Maybe I don't quite understand what it means for some
expression to be 'bottom' (I thought that's the same as 'undefined').

My naive understanding was that a partial function is one which has no
definition for certain arguments; in particular, it has no definition which
could be used while doing equational reasoning by hand, on a piece of paper
(i.e. without running the program).

It appears that this is not quite correct -- instead, any function which
fails to return anything (at runtime!) for certain arguments is partial? E.g.
'sort' would be partial or even 'elem' (consider 'True `elem` repeat False')?

--
Frerich Raabe - [hidden email]
www.froglogic.com - Multi-Platform GUI Testing
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

butrfeld
In reply to this post by Daniel Díaz Casanueva
+1 from me too.

How about also adding in (to the documentation) the pre-condition - i.e. an identification of the inputs for which it will terminate and produce a result
(where this is possible to state, of course).


On 31 Aug 2018, at 03:05, Daniel Díaz Casanueva <[hidden email]> wrote:

+1 from me too. The partiality of a function seems to me like something that should be documented.

Best,
Daniel

Am Fr., 31. Aug. 2018 um 02:10 Uhr schrieb Richard Eisenberg <[hidden email]>:
Proposal: Mark partial functions in `base` as partial

Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.

I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.

Thoughts?

Thanks,
Richard
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--------------------------------------------------------------------
Andrew Butterfield     Tel: +353-1-896-2517     Fax: +353-1-677-2204
Lero@TCD, Head of Foundations & Methods Research Group
School of Computer Science and Statistics,
Room G.39, O'Reilly Institute, Trinity College, University of Dublin
                         http://www.scss.tcd.ie/Andrew.Butterfield/
--------------------------------------------------------------------


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

butrfeld
In reply to this post by David Feuer
Dear David,

given that "data [a] =  [] | (a : [a])" in Haskell is viewed co-inductively and hence admits infinite lists,
then any function f : [a] -> b  is total only if it returns a result.
Does this mean it must terminate?

In a strict world, yes.

In the lazy world, it's a little more complicated than that.

Consider  map id :: [a] -> [a]

is map id partial? It won't terminate if given an infinite list, but it will produce partial results on demand indefinitely - so I say it is total.

However , length applied to [0..] (say) will never return any partial or complete result, and so I would say it's partial.

I too am going to start teaching Haskell newbies, so this is of interest - to what extend to we use "stories for children"

One suggestion: if you don't start with laziness, and they  initially consider lists as finite, then length :: [a] -> Int  is total, where [a] is interpreted as finite lists.
When laziness enters the picture, then points out that having [a] include infinite lists means that some hitherto total function become partial, on that expanded domain.

Perhaps the added documentation should also comment for list and ADT based functions where the infinite forms influence totality/partiality?

Regards, Andrew

On 31 Aug 2018, at 03:09, David Feuer <[hidden email]> wrote:

Yes, I think so. What about functions like length? length (repeat ()) is bottom. repeat () is not bottom. Ergo, length is partial. But I don't think we want to say that!

On Thu, Aug 30, 2018, 10:05 PM Daniel Díaz Casanueva <[hidden email]> wrote:
+1 from me too. The partiality of a function seems to me like something that should be documented.

Best,
Daniel

Am Fr., 31. Aug. 2018 um 02:10 Uhr schrieb Richard Eisenberg <[hidden email]>:
Proposal: Mark partial functions in `base` as partial

Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.

I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.

Thoughts?

Thanks,
Richard
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--------------------------------------------------------------------
Andrew Butterfield     Tel: +353-1-896-2517     Fax: +353-1-677-2204
Lero@TCD, Head of Foundations & Methods Research Group
School of Computer Science and Statistics,
Room G.39, O'Reilly Institute, Trinity College, University of Dublin
                         http://www.scss.tcd.ie/Andrew.Butterfield/
--------------------------------------------------------------------


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Henrik Nilsson-2
In reply to this post by Frerich Raabe
Hi,

Frerich Raabe wrote:

 > On 2018-08-31 04:09, David Feuer wrote:
 > > What about functions like length? length (repeat ()) is bottom.
 > > repeat () is not bottom. Ergo, length is partial.
 >
 > This caught me by surprise - I would have never considered 'length'
 > to be a partial function! Maybe I don't quite understand what it
 > means for some expression to be 'bottom' (I thought that's the same
 > as 'undefined').

We have to be a bit careful with attributing blame for failure.
By David's argument, e.g. "fst" would also be "partial". Consider:

   (_|_, _|_) /= _|_

But

   fst (_|_, _|_) == _|_

But the bottom here does not originate in the computation of "fst" as
such, but in the computation of the *argument* to "fst".

Similarly for "length" above: "length" is not to blame for the
fact that

   length (repeat ()) == _|_

It's simply that computation of the argument to length takes a very(!)
long time.

In a language with strict semantics, this is of course no surprise
at all, and I suspect no one would suggest that a function
like "length" is partial in a strict setting just because the
overall computation fails to terminate when the computation of
an argument does.

 > My naive understanding was that a partial function is one which has
 > no definition for certain arguments; in particular, it has no
 > definition which could be used while doing equational reasoning by
 > hand, on a piece of paper (i.e. without running the program).
 >
 > It appears that this is not quite correct -- instead, any function
 > which fails to return anything (at runtime!) for certain arguments is
 > partial? E.g. 'sort' would be partial or even 'elem' (consider 'True
 > `elem` repeat False')?

I'd say neither "sort" nor "elem" is partial for the same reason.

As to the original suggestion of marking functions as partial, I think
that's fine, as long as one is careful to explain exactly what is meant.
(And documenting (different forms of) strictness would be fine too.)

But one should bear in mind that there are functions that are
partial for other reasons that pattern matching failure, in particular
numerical functions like division, square root, ...
(And the full story of floating point arithmetic with infinities
and NaNs etc. is of course quite complicated.)

Students (well, any programmer) should of course be aware that one have
to be extra careful when using partial functions, and certainly also
encouraged to seek alternative formulations, but just saying "Don't use
partial functions" is not the full story.

Best,

/Henrik





This message and any attachment are intended solely for the addressee
and may contain confidential information. If you have received this
message in error, please contact the sender and delete the email and
attachment.

Any views or opinions expressed by the author of this email do not
necessarily reflect the views of the University of Nottingham. Email
communications with the University of Nottingham may be monitored
where permitted by law.




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Wolfgang Jeltsch-3
In reply to this post by Frerich Raabe
Am Freitag, den 31.08.2018, 08:21 +0200 schrieb Frerich Raabe:

> This caught me by surprise - I would have never considered 'length' to
> be a partial function! Maybe I don't quite understand what it means
> for some expression to be 'bottom' (I thought that's the same as
> 'undefined').
>
> My naive understanding was that a partial function is one which has no
> definition for certain arguments; in particular, it has no definition
> which could be used while doing equational reasoning by hand, on a
> piece of paper (i.e. without running the program).
>
> It appears that this is not quite correct -- instead, any function
> which fails to return anything (at runtime!) for certain arguments is
> partial? E.g. 'sort' would be partial or even 'elem' (consider 'True
> `elem` repeat False')?

The word “partial” might not have a precise definition in the context of
Haskell. In particular, it might not necessarily be defined in terms of
⊥ (bottom). However, the notion of ⊥ itself does have a precise
definition.

⊥ is a special value that every type contains. A consequence of this is
that there are also values like ⊥ : ⊥.

A good way to think about ⊥ is that ⊥ marks the absence of any
information. So the value of an expression is ⊥ if there is a lack of an
appropriate alternative in a case distinction but also if there is a
recursion that doesn’t produce any data.

For example, if zeros is defined via the equation zeroes = 0 : zeroes,
you know that zeroes must be of the form 0 : _; so it cannot be ⊥.
However, if unknown is defined via the equation unknown = unknown, there
is nothing you can learn about any information that unknown would
contain; so unknown is ⊥.

Mathematically, the values of each type form a domain such that ⊥ is the
minimum and each data constructor is an order-preserving function. When
defining a value recursively, Haskell will give you the *least* solution
of the defining equation. The equation zeros = 0 : zeros has only one
solution (0 : 0 : 0 : …). The equation unknown = unknown, on the other
hand, has every value as a solution, and thus the least of them, ⊥, is
picked as the value for unknown.

All the best,
Wolfgang
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Andrew Martin
In reply to this post by Richard Eisenberg-4
I'm strongly +1 on this.

On Thu, Aug 30, 2018 at 8:10 PM Richard Eisenberg <[hidden email]> wrote:
Proposal: Mark partial functions in `base` as partial

Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.

I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.

Thoughts?

Thanks,
Richard
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


--
-Andrew Thaddeus Martin

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

David Feuer
In reply to this post by Wolfgang Jeltsch-3
I think it actually can be made precise, with some more knowledge than I have. Roughly speaking, a function is total if its result is fully defined (contains no bottoms) whenever its argument is fully defined.

On Fri, Aug 31, 2018, 7:04 AM Wolfgang Jeltsch <[hidden email]> wrote:
Am Freitag, den 31.08.2018, 08:21 +0200 schrieb Frerich Raabe:
> This caught me by surprise - I would have never considered 'length' to
> be a partial function! Maybe I don't quite understand what it means
> for some expression to be 'bottom' (I thought that's the same as
> 'undefined').
>
> My naive understanding was that a partial function is one which has no
> definition for certain arguments; in particular, it has no definition
> which could be used while doing equational reasoning by hand, on a
> piece of paper (i.e. without running the program).
>
> It appears that this is not quite correct -- instead, any function
> which fails to return anything (at runtime!) for certain arguments is
> partial? E.g. 'sort' would be partial or even 'elem' (consider 'True
> `elem` repeat False')?

The word “partial” might not have a precise definition in the context of
Haskell. In particular, it might not necessarily be defined in terms of
⊥ (bottom). However, the notion of ⊥ itself does have a precise
definition.

⊥ is a special value that every type contains. A consequence of this is
that there are also values like ⊥ : ⊥.

A good way to think about ⊥ is that ⊥ marks the absence of any
information. So the value of an expression is ⊥ if there is a lack of an
appropriate alternative in a case distinction but also if there is a
recursion that doesn’t produce any data.

For example, if zeros is defined via the equation zeroes = 0 : zeroes,
you know that zeroes must be of the form 0 : _; so it cannot be ⊥.
However, if unknown is defined via the equation unknown = unknown, there
is nothing you can learn about any information that unknown would
contain; so unknown is ⊥.

Mathematically, the values of each type form a domain such that ⊥ is the
minimum and each data constructor is an order-preserving function. When
defining a value recursively, Haskell will give you the *least* solution
of the defining equation. The equation zeros = 0 : zeros has only one
solution (0 : 0 : 0 : …). The equation unknown = unknown, on the other
hand, has every value as a solution, and thus the least of them, ⊥, is
picked as the value for unknown.

All the best,
Wolfgang
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Zemyla
In reply to this post by Andrew Martin
I feel like there's a difference between partial functions in the
sense of length and partial functions in the sense of head.

If you have a partiality monad like the free monad over Identity:

data Partial a = Done a | NotYet (Partial a)

instance Monad Partial where
  return = Done
  Done a >>= f = f a
  NotYet m >>= f = NotYet $ m >>= f

then length has a sensible and productive implementation in terms of it:

partialLength :: [a] -> Partial Int
partialLength = go 0 where
  go n ls = seq n $ case ls of
    [] -> Done n
    _:ls' -> NotYet $ go (n + 1) ls'

This is similar to the mechanism that Agda and Idris use to denote a
potentially non-terminating result; with it, these languages are
Turing complete.

head and tail aren't like that, and should be marked differently in
the documentation.

On Fri, Aug 31, 2018 at 7:28 AM, Andrew Martin
<[hidden email]> wrote:

> I'm strongly +1 on this.
>
> On Thu, Aug 30, 2018 at 8:10 PM Richard Eisenberg <[hidden email]>
> wrote:
>>
>> Proposal: Mark partial functions in `base` as partial
>>
>> Motivation: I'm about to teach Haskell to a classful of beginners. In my
>> experience, they will soon reach for functions like `head` and `tail`,
>> because pattern-matching is foreign to them. I would love just to be able to
>> say "Don't use partial functions", but many students will not easily be able
>> to tell partial functions from total ones.
>>
>> I do expect this problem to work itself out rather quickly, and then
>> students will be able to identify partial functions, but loudly marking
>> partial functions as partial seems like a small service to everyone and a
>> bigger one to newbies. I don't see any downsides.
>>
>> Thoughts?
>>
>> Thanks,
>> Richard
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
>
> --
> -Andrew Thaddeus Martin
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Richard Eisenberg-4
In reply to this post by Richard Eisenberg-4
In a response not cc'd to the list, a contributor (not sure if they want public identification) suggests:

> I think we want something like "partial even given input you can successfully DeepSeq"

That's the specification of the feature I'm after. I think all the commentary about infinite lists, etc., would lead also to good documentation additions. (For example, it would be fantastic if every function precisely documented its strictness, preferably with some standard notation, but this is not the problem I'm trying to solve here.)

Also, it was suggested that the documentation be checked -- that is, we could imagine a {-# TOTAL ... #-} or {-# PARTIAL ... #-} pragma that GHC could check on compilation and Haddock could include in the documentation. This would also be great, but much more than I'm proposing here.

Maybe here's a concrete example:

> -- | /Contains a call to 'error'./ Extract the first element of a list, which must be non-empty.
> head                    :: [a] -> a

In the end, it's the call to error that I want noted. Of course, having a similar note on functions like div (where the problem isn't a call to error) and length (that will loop on infinite lists) is good, but not really what I'm proposing here.

Thanks,
Richard

> On Aug 30, 2018, at 8:10 PM, Richard Eisenberg <[hidden email]> wrote:
>
> Proposal: Mark partial functions in `base` as partial
>
> Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.
>
> I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.
>
> Thoughts?
>
> Thanks,
> Richard
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

David Feuer
Why isn't the call to error in div what you mean?

On Fri, Aug 31, 2018, 10:49 AM Richard Eisenberg <[hidden email]> wrote:
In a response not cc'd to the list, a contributor (not sure if they want public identification) suggests:

> I think we want something like "partial even given input you can successfully DeepSeq"

That's the specification of the feature I'm after. I think all the commentary about infinite lists, etc., would lead also to good documentation additions. (For example, it would be fantastic if every function precisely documented its strictness, preferably with some standard notation, but this is not the problem I'm trying to solve here.)

Also, it was suggested that the documentation be checked -- that is, we could imagine a {-# TOTAL ... #-} or {-# PARTIAL ... #-} pragma that GHC could check on compilation and Haddock could include in the documentation. This would also be great, but much more than I'm proposing here.

Maybe here's a concrete example:

> -- | /Contains a call to 'error'./ Extract the first element of a list, which must be non-empty.
> head                    :: [a] -> a

In the end, it's the call to error that I want noted. Of course, having a similar note on functions like div (where the problem isn't a call to error) and length (that will loop on infinite lists) is good, but not really what I'm proposing here.

Thanks,
Richard

> On Aug 30, 2018, at 8:10 PM, Richard Eisenberg <[hidden email]> wrote:
>
> Proposal: Mark partial functions in `base` as partial
>
> Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.
>
> I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.
>
> Thoughts?
>
> Thanks,
> Richard
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Mark partial functions as such

Richard Eisenberg-4
Because I was silly and didn't look for it. That can and should be included, yes.

On Aug 31, 2018, at 10:53 AM, David Feuer <[hidden email]> wrote:

Why isn't the call to error in div what you mean?

On Fri, Aug 31, 2018, 10:49 AM Richard Eisenberg <[hidden email]> wrote:
In a response not cc'd to the list, a contributor (not sure if they want public identification) suggests:

> I think we want something like "partial even given input you can successfully DeepSeq"

That's the specification of the feature I'm after. I think all the commentary about infinite lists, etc., would lead also to good documentation additions. (For example, it would be fantastic if every function precisely documented its strictness, preferably with some standard notation, but this is not the problem I'm trying to solve here.)

Also, it was suggested that the documentation be checked -- that is, we could imagine a {-# TOTAL ... #-} or {-# PARTIAL ... #-} pragma that GHC could check on compilation and Haddock could include in the documentation. This would also be great, but much more than I'm proposing here.

Maybe here's a concrete example:

> -- | /Contains a call to 'error'./ Extract the first element of a list, which must be non-empty.
> head                    :: [a] -> a

In the end, it's the call to error that I want noted. Of course, having a similar note on functions like div (where the problem isn't a call to error) and length (that will loop on infinite lists) is good, but not really what I'm proposing here.

Thanks,
Richard

> On Aug 30, 2018, at 8:10 PM, Richard Eisenberg <[hidden email]> wrote:
>
> Proposal: Mark partial functions in `base` as partial
>
> Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones.
>
> I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides.
>
> Thoughts?
>
> Thanks,
> Richard
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
12