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. Re: How to avoid repeating a type restriction from a data
constructor (gs)
2. Re: How to avoid repeating a type restriction from a data
constructor (Daniel Fischer)
3. Re: How to avoid repeating a type restriction from a data
constructor (gs)
4. Re: How to avoid repeating a type restriction from a data
constructor (Daniel Fischer)
5. Re: How to avoid repeating a type restriction from a data
constructor (gs)
6. Re: How to avoid repeating a type restriction from a data
constructor (Daniel Fischer)
7. Re: How to avoid repeating a type restriction from a data
constructor (gs)
8. Re: How to avoid repeating a type restriction from a data
constructor (Daniel Fischer)
9. Re: What is the functional way of implementing a function
that takes a long time to execute? (Bryce Verdier)
----------------------------------------------------------------------
Message: 1
Date: Wed, 24 Apr 2013 10:35:34 +0000 (UTC)
From: gs <[email protected]>
Subject: Re: [Haskell-beginners] How to avoid repeating a type
restriction from a data constructor
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Daniel Fischer <daniel.is.fischer <at> googlemail.com> writes:
> Use a GADT,
>
> {-# LANGUAGE GADTs #-}
>
> data Source x y where
> Source :: Variable v => { bindings :: v [Binding a], var :: v a }
> -> Source v a
I tried this, but every place that I remove the restriction Variable v =>
from something using Source, I get an error No instance for (Variable v) ...
------------------------------
Message: 2
Date: Wed, 24 Apr 2013 14:00:07 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] How to avoid repeating a type
restriction from a data constructor
To: [email protected]
Cc: gs <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
On Wednesday 24 April 2013, 10:35:34, gs wrote:
> Daniel Fischer <daniel.is.fischer <at> googlemail.com> writes:
> > Use a GADT,
> >
> > {-# LANGUAGE GADTs #-}
> >
> > data Source x y where
> >
> > Source :: Variable v => { bindings :: v [Binding a], var :: v a }
> >
> > -> Source v a
>
> I tried this, but every place that I remove the restriction Variable v =>
> from something using Source, I get an error No instance for (Variable v) ...
Sounds like you're not pattern-matching on the `Source` constructor.
Can you post some example code?
------------------------------
Message: 3
Date: Wed, 24 Apr 2013 12:27:23 +0000 (UTC)
From: gs <[email protected]>
Subject: Re: [Haskell-beginners] How to avoid repeating a type
restriction from a data constructor
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Daniel Fischer <daniel.is.fischer <at> googlemail.com> writes:
> > > data Source x y where
> > >
> > > Source :: Variable v => { bindings :: v [Binding a], var :: v a }
> > >
> > > -> Source v a
> >
> > I tried this, but every place that I remove the restriction Variable v =>
> > from something using Source, I get an error No instance for (Variable v) ...
>
> Sounds like you're not pattern-matching on the `Source` constructor.
>
> Can you post some example code?
http://code.accursoft.com/binding/src/c13ccbbec0ba8e326369ff2252863f20a891ef76/binding-core/src/Data/Binding/Simple.hs
http://code.accursoft.com/binding/src/c13ccbbec0ba8e326369ff2252863f20a891ef76/binding-core/src/Data/Binding/List.hs
------------------------------
Message: 4
Date: Wed, 24 Apr 2013 14:43:58 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] How to avoid repeating a type
restriction from a data constructor
To: [email protected]
Cc: gs <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
On Wednesday 24 April 2013, 12:27:23, gs wrote:
> Daniel Fischer <daniel.is.fischer <at> googlemail.com> writes:
> >
> > Can you post some example code?
>
> http://code.accursoft.com/binding/src/c13ccbbec0ba8e326369ff2252863f20a891ef
> 76/binding-core/src/Data/Binding/Simple.hs
>
> http://code.accursoft.com/binding/src/c13ccbbec0ba8e326369ff2252863f20a891ef
> 76/binding-core/src/Data/Binding/List.hs
I meant example code using a GADT for Source, and not DatatypeContexts; and
some function where you still need the context.
------------------------------
Message: 5
Date: Wed, 24 Apr 2013 13:25:01 +0000 (UTC)
From: gs <[email protected]>
Subject: Re: [Haskell-beginners] How to avoid repeating a type
restriction from a data constructor
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Daniel Fischer <daniel.is.fischer <at> googlemail.com> writes:
> I meant example code using a GADT for Source, and not DatatypeContexts; and
> some function where you still need the context.
OK, here are some truncated instances/functions:
data Source v a where
Source :: Variable v => {bindings :: v [Binding a] ,var :: v a} -> Source v a
instance Variable v => Variable (Source v) where
newVar a = do bindings <- newVar []
v <- newVar a
return $ Source bindings v
instance Variable v => Bindable (Source v) where
bind (Source bindings var) extract target apply =
do let binding = Binding extract target apply
--update the new binding
a <- readVar var
data BindingList v a where
BindingList :: Variable v => {source :: Source v a, list :: v [v a],pos
:: v Int} -> BindingList v a
fromBindingList :: Variable v => BindingList v a -> IO [a]
fromBindingList b = do update b
readVar (list b) >>= mapM readVar
instance Variable v => Bindable (BindingList v) where
bind = bind . source
------------------------------
Message: 6
Date: Wed, 24 Apr 2013 16:08:23 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] How to avoid repeating a type
restriction from a data constructor
To: [email protected]
Cc: gs <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
On Wednesday 24 April 2013, 13:25:01, gs wrote:
> Daniel Fischer <daniel.is.fischer <at> googlemail.com> writes:
> > I meant example code using a GADT for Source, and not DatatypeContexts;
> > and
> > some function where you still need the context.
>
> OK, here are some truncated instances/functions:
>
> data Source v a where
> Source :: Variable v => {bindings :: v [Binding a] ,var :: v a} -> Source
> v a
>
> instance Variable v => Variable (Source v) where
> newVar a = do bindings <- newVar []
> v <- newVar a
> return $ Source bindings v
>
> instance Variable v => Bindable (Source v) where
> bind (Source bindings var) extract target apply =
> do let binding = Binding extract target apply
> --update the new binding
> a <- readVar var
Removing the `Variable v` context from instance declarations is at least
tricky. I don't think you can do it at all here. For the context to become
available, you need to pattern-match, but in `newVar`, the `Source` appears
only as the result. Therefore you need the `Variable v` context to be able to
write
v <- newVar a
Consequently, you can't have an
instance Variable (Source v) where ...
without context, and since `Variable b` is a superclass constraint on
`Bindable b`, you need something that guarantees that `Source x` (resp.
`BindingList x`) has a `Variable` instance.
>
> data BindingList v a where
> BindingList :: Variable v => {source :: Source v a, list :: v [v a],pos
>
> :: v Int} -> BindingList v a
>
> fromBindingList :: Variable v => BindingList v a -> IO [a]
> fromBindingList b = do update b
> readVar (list b) >>= mapM readVar
You're not pattern-matching on the constructor. I wrote that you have to do
that to make the context available:
> > The `Variable v` context becomes available by pattern-matching on the
constructor `Source` (but not by using the field names to deconstruct a value
of type `Source v a`!).
Pattern-matching,
fromBindingList :: BindingList v a -> IO [a]
fromBindingList b@(BindingList s l p)
= do update b
readVar l >>= mapM readVar
removes the need to mention the `Variable v` context.
------------------------------
Message: 7
Date: Wed, 24 Apr 2013 14:19:35 +0000 (UTC)
From: gs <[email protected]>
Subject: Re: [Haskell-beginners] How to avoid repeating a type
restriction from a data constructor
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Daniel Fischer <daniel.is.fischer <at> googlemail.com> writes:
> Removing the `Variable v` context from instance declarations is at least
> tricky. I don't think you can do it at all here. For the context to become
> available, you need to pattern-match, but in `newVar`, the `Source` appears
> only as the result. Therefore you need the `Variable v` context to be able to
> write
>
> v <- newVar a
>
> Consequently, you can't have an
>
> instance Variable (Source v) where ...
>
> without context, and since `Variable b` is a superclass constraint on
> `Bindable b`, you need something that guarantees that `Source x` (resp.
> `BindingList x`) has a `Variable` instance.
>
>
> You're not pattern-matching on the constructor. I wrote that you have to do
> that to make the context available:
Thank you, I understand now. So as far as removing redundant code is
concerned, this can't really be done? The instance declarations still need
the redundant context, and function definitions need a redundant
pattern-matching instead of a redundant context.
------------------------------
Message: 8
Date: Wed, 24 Apr 2013 17:10:45 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] How to avoid repeating a type
restriction from a data constructor
To: [email protected]
Cc: gs <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
On Wednesday 24 April 2013, 14:19:35, gs wrote:
> So as far as removing redundant code is
> concerned, this can't really be done?
That depends. Your example is not well-suited for that. In other situations,
you can get rid of contexts well.
> The instance declarations still need the redundant context,
Well, the context is not redundant, that's the crux.
You can specify the type `Source v a` even when there is no `Variable v`
instance [whether you use DatatypeContexts - which, again, are pretty useless
because they don't do what one would expect - or GADTs]. And such a type is
inhabited by bottom, you just can't create non-bottom values of such a type.
Hence the `Variable v` context gives additional information that is needed for
the instance.
If you had a `v a` as argument in all methods of `class Variable v`, you could
write the
instance Variable (Source v) where ...
without the `Variable v` context by pattern-matching on `Source` to make the
`v` instance available (when using GADTs), then you wouldn't need the
`Variable v` context on the `Bindable` instance either (similarly for
BindingList).
But to have a usable `newVar`, you need the context, and that propagates.
> and function definitions need a redundant pattern-matching
> instead of a redundant context.
The pattern-matching isn't redundant either.
But all in all, basically you have the choice between adding a context or
pattern-matching for stuff like that.
------------------------------
Message: 9
Date: Wed, 24 Apr 2013 09:28:35 -0700
From: Bryce Verdier <[email protected]>
Subject: Re: [Haskell-beginners] What is the functional way of
implementing a function that takes a long time to execute?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
Thank you Ertugrul for this awesome explanation.
It's emails like that are the reason why I love this list.
Bryce
On 04/23/2013 06:28 AM, Ertugrul S?ylemez wrote:
> "Costello, Roger L." <[email protected]> wrote:
>
>> Suppose a function takes a long time to do its work.
>>
>> Perhaps it takes minutes or even hours to complete.
>>
>> While it is crunching along, it would be nice to have some insight
>> into its status such as (1) how close is it to completing? (2) what
>> part of the task is it currently working on?
>>
>> It might even be nice to be notified when it is finished.
>>
>> What is the functional way of implementing the function?
> The traditional way in Haskell to see intermediate results is not to
> produce the final result only, but to produce a list of intermediate
> results, the last of which is the final result. The trick is to apply
> what we call corecursion, which basically means: Wrap the recursion in
> an (ideally nonstrict) data constructor cell. The function
>
> sqrtApprox :: Rational -> Rational
>
> then becomes:
>
> sqrtApprox :: Rational -> [Rational]
>
> You know that you have done it properly if you used proper corecursion,
> which looks similar to this:
>
> loop x y = (x, y) : loop x' y'
> where
> x' = {- ... -}
> y' = {- ... -}
>
> The important part is that the recursion is the right argument of the
> constructor (:) and that the constructor application is the last thing
> that happens. You can make sure that you have done it properly and even
> get some nice deforestation optimizations by using one of the predefined
> corecursion operators like 'unfoldr', 'iterate', etc.
>
> Sometimes you'll want to encode an algorithm even as a composition of
> predefined corecursive formulas like 'map', 'filter', 'tails', etc. For
> example you may have a list [1,2,3,4,5,6,7,8,9] to begin with and you
> want to encode the sum of the products of three consecutive values,
> 1*2*3 + 4*5*6 + 7*8*9 + 10:
>
> takeWhile (not . null) . map (take 3) . iterate (drop 3)
>
> Now how do we produce online statistics while this algorithm calculates
> its result? This is the easiest part, but there is a catch. You have a
> corecursively produced list, which ensures that the list is lazy enough.
> All you have to do now is to consume the list as part of an IO action.
> The foldM combinator is most helpful here:
>
> sumStats :: (Num a) => [a] -> IO a
> sumStats = foldM f 0
> where
> f s x = do
> putStrLn ("Sum so far: " ++ s)
> return (s + x)
>
> As said there is a catch. In your recursive consumer you actually have
> to make sure that the intermediate result is actually calculated. This
> is important, because otherwise your consumer doesn't actually force the
> calculation, but really just builds up a large unevaluated expression,
> which is only evaluated at the very end.
>
> The easiest way to ensure this is to just do what I did in sumStats:
> Print the intermediate result (you may call it 'state') or some value
> derived from it (make sure that the value depends on the entire state).
> If you don't want to perform some IO action with the state you can also
> just be strict. There are many ways to be strict, my favorite being
>
> f s x = do
> {- ... -}
> return $! s + x
>
> but you can also use the BangPatterns extension.
>
> The basic idea of all this is that you turn an opaque monolithic formula
> into a stream processing formula. This not only makes it more flexible,
> but may also help you understand the original problem better and split
> it into independent modules. Remember that you can always compose
> stream processors using regular function composition as done above.
>
> Once you are comfortable with using lists for stream processing you can
> also use an actual stream processing abstraction. My personal favorite
> right now is the 'pipes' library, but there are other useful libraries
> including the other modern library 'conduit' as well as the traditional
> 'enumerator' library.
>
> This of course does not end with streams. Streams are for algorithms
> with a linear execution paths, but not every algorithm follows that. If
> your formula naturally follows multiple paths, there is nothing wrong
> with corecursively producing and recursively consuming trees or graphs,
> for example. You just need unfoldTree+foldTreeM or
> unfoldGraph+foldGraphM for that. This works with every algebraic data
> structure.
>
> As a final remark, don't worry about the performance. Haskell is a lazy
> language. Done properly at least the intermediate lists will be
> optimized away by the compiler and the resulting machine code is close
> to what a C compiler would have produced for the original monolithic
> formula randomly interspersed with statistics printing commands.
>
>
> Greets
> Ertugrul
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20130424/b53166ca/attachment.htm>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 58, Issue 37
*****************************************
