Re: [Haskell-cafe] Re: A free monad theorem?
On Fri, Sep 01, 2006 at 01:13:14AM +0200, Benjamin Franksen wrote: > So getting the value out of the monad is not a pure function (extract :: > Monad m => m a -> a). I think I stated that, already, in my previous post. The only generic way of "extracting" values from a monadic value is the bind operator. The lack of extract function is a feature :-) But now I know that you are not really claiming such a function exists. > The real question (the one that bugs me, anyway) is if one can give a > precise meaning to the informal argument that if the definition of bind is > to be non-trivial then its second argument must be applied to some > non-trivial value at one point (but not, of course, in all cases, nor > necessarily only once) How about using monad laws, specifically: (return x) >>= f == f x We assume that >>= never uses it's second argument, so: (return x) >>= f == (return x) >>= g Combining it with the above monad law we get: f x == (return x) >>= f == (return x) >>= g == g x so f x = g x for arbitrary f and g. Let's substitute return for f and undefined for g: return x = undefined x so return x = undefined Now that seems like a very trivial (and dysfunctional) monad. > and that this implies that the computation represented by the first > argument must somehow be 'run' (in some environment) in order to > produce such a value. Not sure what to do with this one. Certainly, for some monads the environment can be empty, eg. for Identity or []. For the IO monad the lack of the "run" function is a feature (Let's pretend that unsafePerformIO doesn't exist - in fact, there is no such function in Haskell 98), but you can say that the RTS runs the "main" IO computation. Informally, it seems obvious that you have to be able to run your monadic computations somehow - otherwise you wouldn't be writing them ;-) I am not sure you can prove it though. > -- And, of course, whether this is actually true in the first place. > Would you say that your examples above are counter-examples to this > statement (imprecise as it is, unfortunately)? Well, no, they were counter-examples for the existence of the extract function. As you say, I misunderstood you intent. Best regards Tomasz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HaXml question
Tim Newsham <[EMAIL PROTECTED]> writes:
> I thought this one would be easy but I'm starting to think its not.
> I am playing with HaXml and I want to transform an XML tree into
> another tree. The transforms are simple enough, but the kicker
> is that I want them to be "stateful." In this example, the state
> is a random number generator. So the transformation depends on
> the current node and the random number generator state. I want
> to transform every node in the tree.
Indeed, the HaXml functions are pure, and in particular foldXml does
not thread a state through.
To introduce state, you provide your own state monad (fortunately
there is always Control.Monad.State). To traverse the whole tree in
this monad, you write your own recursion and deconstruct the nodes
yourself (because foldXml is too specific to be re-usable).
Here is my example. It replaces attribute values by random integers
between 0 and 99, so it is a similar task but slightly different from
yours. Some names are inspired by yours, but I have simplified their
nature: The state I thread through is not a stream of generators, but
rather a stream of numbers; as long as this stream comes from
Random.randomRs, I'm good.
import Text.XML.HaXml
import Control.Monad.State
import Random
newtweak :: [Int] -> CFilter
newtweak xs c = [evalState (reco c) xs]
reco :: Content -> State [Int] Content
reco (CElem (Elem nm ats cs)) =
do { ats' <- mapM newtweakAttr ats
; cs' <- mapM reco cs
; return (CElem (Elem nm ats' cs'))
}
reco c = return c
newtweakAttr (k,_) =
do { n <- gets head
; modify tail
; return (k, AttValue[Left (show n)])
}
main = do
gen <- getStdGen
processXmlWith (newtweak (randomRs (0,99) gen))
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: A free monad theorem?
> So getting the value out of the monad is not a pure function (extract :: > Monad m => m a -> a). I think I stated that, already, in my previous post. > I'd even say that the monadic values alone can be completely meaningless. > They often have a meaning only relative to some environment, thus are > (usually) _effectful_ computations. But we already knew that, didn't we? It may help to remember that, in the mathematical context where monads where born (AKA category theory), a monad is generally defined as a functor with a join and a unit (satisfying some laws that I would have to look up). The unit should be familiar (it's spelled 'return' in haskell), but join may not be. Its type is join :: Monad m => m (m a) -> m a which is a lot like extract, except with one more "monad layer" wrapped around it. IIRC the relevant identity here is: x >>= f === join (fmap f x) and with f specialzed to id: join (fmap id x) === x >>= id join x === x >>= id I'm not sure why (>>=) is taken as basic in Haskell. At any rate, my point is that I think your questions might be better framed in terms of the behavior of 'fmap'. > The real question (the one that bugs me, anyway) is if one can give a > precise meaning to the informal argument that if the definition of bind is > to be non-trivial then its second argument must be applied to some > non-trivial value at one point (but not, of course, in all cases, nor > necessarily only once), and that this implies that the computation > represented by the first argument must somehow be 'run' (in some > environment) in order to produce such a value. -- And, of course, whether > this is actually true in the first place. Would you say that your examples > above are counter-examples to this statement (imprecise as it is, > unfortunately)? > Ben -- Rob Dockins Talk softly and drive a Sherman tank. Laugh hard, it's a long way to the bank. -- TMBG ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: A free monad theorem?
Tomasz Zielonka wrote:
> On Thu, Aug 31, 2006 at 07:23:55PM +0200, Benjamin Franksen wrote:
>> I'd like to know if the following reasoning can be made more precise:
>>
>> As we all know, the monadic bind operation has type:
>>
>> bind :: Monad m => m a -> (a -> m b) -> m b
>>
>> My intuition says that in order to apply the second argument to some
>> non-trivial (i.e. non-bottom) value of type a, the bind operator needs to
>> be able to somehow 'extract' a value (of type a) from the first argument
>> (of type m a).
>
> The bind operator doesn't have to neccesarily apply the second argument
> to anything. What if m is Maybe, and the first arguments is Nothing?
True, however if the instance for Maybe would have been defined
without /ever/ applying the second argument to anything, then wouldn't this
necessarily be a trivial monad (however one would need to define 'trivial'
here)?
> And if the bind operator "wants" to apply the second argument to
> something, it doesn't have to do it only once - consider the [] monad.
Yes, I should have said: Any non-trivial definition of bind has to apply its
second argument at least in _some_ cases and _at least_ once to something
non-bottom.
> Other examples:
>
> get :: State s s-- from Control.Monad.State
>
> there is no way you can extract an 's' value from "get" alone -
> you have to supply the state to the whole computation
>
> Cont (const ()) :: Cont () a-- from Control.Monad.Cont
>
> whatever you do, you won't be able to extract an 'a' typed
> value, non-bottom from this computation. Cont is defined as:
>
> newtype Cont r a = Cont {runCont :: (a -> r) -> r)}
So getting the value out of the monad is not a pure function (extract ::
Monad m => m a -> a). I think I stated that, already, in my previous post.
I'd even say that the monadic values alone can be completely meaningless.
They often have a meaning only relative to some environment, thus are
(usually) _effectful_ computations. But we already knew that, didn't we?
The real question (the one that bugs me, anyway) is if one can give a
precise meaning to the informal argument that if the definition of bind is
to be non-trivial then its second argument must be applied to some
non-trivial value at one point (but not, of course, in all cases, nor
necessarily only once), and that this implies that the computation
represented by the first argument must somehow be 'run' (in some
environment) in order to produce such a value. -- And, of course, whether
this is actually true in the first place. Would you say that your examples
above are counter-examples to this statement (imprecise as it is,
unfortunately)?
Ben
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A free monad theorem?
Il Thu, Aug 31, 2006 at 07:23:55PM +0200, Benjamin Franksen ebbe a scrivere: > I argued that monadic values get 'chained' in a very specific way and that > in order to get an intuition about what this monadic chaining really means > on the most general level, the standard model of 'computation that returns > a value of type a' is the appropriate one. If you pardon my ascii art, you can have a look here, where I try to visualize what bind does. http://www.haskell.org/haskellwiki/The_Monadic_Way#What_Does_Bind_Bind.3F Monad is of type M (Int,String) with (>>=) m f = (b, x ++ y) where (a, x) = m (b, y) = f a I don't know if this helps. Andrea ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Re: Re: data structures question
Chris Kuklewicz wrote: > Benjamin Franksen wrote: >> Chris Kuklewicz wrote: >>> I did not even run the code I wrote through ghci, I was just showing >>> what it could look like. >>> >>> And stop calling me Shirley. [...] >> Could you please be a bit more explicit? Have I offended anyone? Or else, >> how do I have to understand this comment other than as a rebuke? And how >> comes you answer this as if you were the one who posted the code, and not >> a person named Matthias Fischmann? > > Sorry for the misunderstanding. No one has been offended or given > offense. > The Surely/Shirley is a reference to the classic 1980 motion picture > "Airplane!" in which the humor includes a repeated motif [1]: > >> Rumack: Mr. Striker, the passengers are getting worse. You must land >> soon. Ted Striker: Surely there must be something you can do. >> Rumack: I'm doing everything I can... and stop calling me Shirley. > >> Ted Striker: Surely you can't be serious. >> Rumack: I am serious... and don't call me Shirley. > > Nothing was offensive or arrogant.I just saw it as an opportunity to > reference the joke. Ahh, I'm very glad to hear that. It seems the misunderstanding was completely on my part. Did a little research and found quite a number for websites citing dialogs from this movie. I begin to understand that it must have been cult... > I am sorry my other posting was off topic. Sometimes I contribute what > occurs to me instead of what is relevant. I can happily live with that ;-) (although I'd still be interested what prompted you to post this code which I admittedly did not fully understand). And sorry for dragging this (completely off-topic) stuff out here on the list. I'll shut up now. Cheers, Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A free monad theorem?
On Thu, Aug 31, 2006 at 10:16:38PM +0200, Tomasz Zielonka wrote: > Cont (const ()) :: Cont () a-- from Control.Monad.Cont > > whatever you do, you won't be able to extract an 'a' typed > value, non-bottom from this computation. Unless you substitute () for 'a', of course :-) Best regards Tomasz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A free monad theorem?
On Thu, Aug 31, 2006 at 07:23:55PM +0200, Benjamin Franksen wrote:
> I'd like to know if the following reasoning can be made more precise:
>
> As we all know, the monadic bind operation has type:
>
> bind :: Monad m => m a -> (a -> m b) -> m b
>
> My intuition says that in order to apply the second argument to some
> non-trivial (i.e. non-bottom) value of type a, the bind operator needs to
> be able to somehow 'extract' a value (of type a) from the first argument
> (of type m a).
The bind operator doesn't have to neccesarily apply the second argument
to anything. What if m is Maybe, and the first arguments is Nothing?
And if the bind operator "wants" to apply the second argument to
something, it doesn't have to do it only once - consider the [] monad.
Other examples:
get :: State s s-- from Control.Monad.State
there is no way you can extract an 's' value from "get" alone -
you have to supply the state to the whole computation
Cont (const ()) :: Cont () a-- from Control.Monad.Cont
whatever you do, you won't be able to extract an 'a' typed
value, non-bottom from this computation. Cont is defined as:
newtype Cont r a = Cont {runCont :: (a -> r) -> r)}
Best regards
Tomasz
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Re: data structures question
Benjamin Franksen wrote: Chris Kuklewicz wrote: Benjamin Franksen wrote: Matthias Fischmann wrote: The trick is that Int is not the only index data type, but tuples of index data types are, too. Do this: | type Point = (State, State, Int) | type TypeV = Array State Double | | matrix :: TypeV | matrix = array bounds values |where |... Surely you meant to say | type TypeV = Array Point Double True, I did make that mistake. Cheers, Ben And type Value = Double newtype PointNat = PointNat Int deriving (...Ix) type Point = (State,State,PointNat) Or even type TypeVof a = Array PointNat a type TypeV = TypeVof Value I did not even run the code I wrote through ghci, I was just showing what it could look like. And stop calling me Shirley. Dear Chris, Could you please be a bit more explicit? Have I offended anyone? Or else, how do I have to understand this comment other than as a rebuke? And how comes you answer this as if you were the one who posted the code, and not a person named Matthias Fischmann? Sorry for the misunderstanding. No one has been offended or given offense. The Surely/Shirley is a reference to the classic 1980 motion picture "Airplane!" in which the humor includes a repeated motif [1]: Rumack: Mr. Striker, the passengers are getting worse. You must land soon. Ted Striker: Surely there must be something you can do. Rumack: I'm doing everything I can... and stop calling me Shirley. Ted Striker: Surely you can't be serious. Rumack: I am serious... and don't call me Shirley. Please note that English is not my native tongue so there is always the possibility that I misunderstood something, or that I express myself badly and so cause misunderstandings. Is the expression "Surely you meant to say " perceived as offending or arrogant, perhaps? In this case I would gladly apologize and assure everyone that this was not intended! Nothing was offensive or arrogant.I just saw it as an opportunity to reference the joke. I posted this correction only in order to avoid confusion for the OP, who described himself as a beginner with regard to Haskell. I didn't mean to be nitpicking or anything like that. If I have made a mistake, either technically or by chosing the wrong words, then please tell me so. Your answer to my other posting today is of a similar nature, i.e. completely obscure to me, and totally disregarding the essence of my question. If there is something personal involved here (for which I can't imagine any reason other than the above mentioned one) maybe it would be better to clearly say so (and sort this out in private and not on this list). I am sorry my other posting was off topic. Sometimes I contribute what occurs to me instead of what is relevant. Cheers, Chris [1] http://www.imdb.com/title/tt0080339/quotes ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Re: data structures question
> And stop calling me Shirley. Could you please be a bit more explicit? Have I offended anyone? This is a reference to a joke from the movie Airplane: "Surely, you can't be serious." "I am serious, and stop calling me Shirley." I imagine it meant nothing personal. Jared. -- http://www.updike.org/~jared/ reverse ")-:" ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Re: data structures question
Chris Kuklewicz wrote: > Benjamin Franksen wrote: >> Matthias Fischmann wrote: >>> The trick is that Int is not the only index data type, but tuples of >>> index data types are, too. Do this: >>> >>> | type Point = (State, State, Int) >>> | type TypeV = Array State Double >>> | >>> | matrix :: TypeV >>> | matrix = array bounds values >>> |where >>> |... >> >> Surely you meant to say >> >> | type TypeV = Array Point Double >> >> Cheers, >> Ben > > And > > type Value = Double > newtype PointNat = PointNat Int deriving (...Ix) > type Point = (State,State,PointNat) > > Or even > > type TypeVof a = Array PointNat a > type TypeV = TypeVof Value > > I did not even run the code I wrote through ghci, I was just showing what > it could look like. > > And stop calling me Shirley. Dear Chris, Could you please be a bit more explicit? Have I offended anyone? Or else, how do I have to understand this comment other than as a rebuke? And how comes you answer this as if you were the one who posted the code, and not a person named Matthias Fischmann? Please note that English is not my native tongue so there is always the possibility that I misunderstood something, or that I express myself badly and so cause misunderstandings. Is the expression "Surely you meant to say " perceived as offending or arrogant, perhaps? In this case I would gladly apologize and assure everyone that this was not intended! I posted this correction only in order to avoid confusion for the OP, who described himself as a beginner with regard to Haskell. I didn't mean to be nitpicking or anything like that. If I have made a mistake, either technically or by chosing the wrong words, then please tell me so. Your answer to my other posting today is of a similar nature, i.e. completely obscure to me, and totally disregarding the essence of my question. If there is something personal involved here (for which I can't imagine any reason other than the above mentioned one) maybe it would be better to clearly say so (and sort this out in private and not on this list). Clueless, Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: A free monad theorem?
Chris Kuklewicz wrote:
> Benjamin Franksen wrote:
>> I'd like to know if the following reasoning can be made more precise:
>>
>> As we all know, the monadic bind operation has type:
>>
>> bind :: Monad m => m a -> (a -> m b) -> m b
>>
>> My intuition says that in order to apply the second argument to some
>> non-trivial (i.e. non-bottom) value of type a, the bind operator needs to
>> be able to somehow 'extract' a value (of type a) from the first argument
>> (of type m a). I would like to argue that this is because bind is
>> polymorphic in a, which makes it impossible to construct values of type
>> a 'out of thin air' (besides bottom). Thus, however bind is defined, the
>> only place where it can obtain a 'real' value of type a is from its first
>> argument. Although one might think that this implies the existence of
>> some function
>>
>> extract :: Monad m => m a -> a
>>
>> it is obvious that this is too limiting, as the IO monad plainly shows.
>> Even monads that can be implemented in Haskell itself (the vast majority,
>> it seems) usually need some additional (monad-specific) argument to
>> their 'extract' (or 'run') function. However, even a value of type IO
>> a /does/ produce a value of type a, only the 'value producing
>> computation' is not a (pure) function. But how can all this be made more
>> precise with less handwaiving?
>
> You can cheat a bit and write your own IO a -> a using GHC:
>
> {-
> Taken from the shootout at
>
http://shootout.alioth.debian.org/gp4/benchmark.php?test=knucleotide&lang=ghc&id=2
> -}
>
> import GHC.Exts -- for realWorld# value
> import GHC.IOBase -- for IO constructor
>
> {-# INLINE inlinePerformIO #-}
> inlinePerformIO :: IO a -> a
> inlinePerformIO (IO m) = case m realWorld# of (# _, r #) -> r
>
> -- Now you can write things like this, which need IO action to define pure
> -- functions:
>
> data Seq = Seq !Int !(Ptr Base)
>
> instance Eq Seq where
> (==) (Seq (I# size1) (Ptr ptr1)) (Seq _ (Ptr ptr2)) = inlinePerformIO $
> IO
> (\s -> eqmem size1 ptr1 ptr2 s)
> {-# INLINE eqmem #-}
> eqmem remainingSize ptr1 ptr2 s = if remainingSize ==# 0# then (# s , True
> #)
>else case readInt8OffAddr# ptr1 0# s of { (# s, i8a #) ->
> case readInt8OffAddr# ptr2 0# s of { (# s, i8b #) ->
>if i8a /=# i8b then (# s, False #)
>else eqmem (remainingSize -# 1#) (plusAddr# ptr1 1#)
>(plusAddr#
> ptr2 1#) s } }
Would you (or someone else) care to explain what this exercise in advanced
ghc hacking has to do with my question? I don't exclude the remote
possibility that there is some connection but I don't get it.
Ben
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A free monad theorem?
Benjamin Franksen wrote:
I'd like to know if the following reasoning can be made more precise:
As we all know, the monadic bind operation has type:
bind :: Monad m => m a -> (a -> m b) -> m b
My intuition says that in order to apply the second argument to some
non-trivial (i.e. non-bottom) value of type a, the bind operator needs to
be able to somehow 'extract' a value (of type a) from the first argument
(of type m a). I would like to argue that this is because bind is
polymorphic in a, which makes it impossible to construct values of type
a 'out of thin air' (besides bottom). Thus, however bind is defined, the
only place where it can obtain a 'real' value of type a is from its first
argument. Although one might think that this implies the existence of some
function
extract :: Monad m => m a -> a
it is obvious that this is too limiting, as the IO monad plainly shows. Even
monads that can be implemented in Haskell itself (the vast majority, it
seems) usually need some additional (monad-specific) argument to
their 'extract' (or 'run') function. However, even a value of type IO
a /does/ produce a value of type a, only the 'value producing computation'
is not a (pure) function. But how can all this be made more precise with
less handwaiving?
You can cheat a bit and write your own IO a -> a using GHC:
{-
Taken from the shootout at
http://shootout.alioth.debian.org/gp4/benchmark.php?test=knucleotide&lang=ghc&id=2
-}
import GHC.Exts -- for realWorld# value
import GHC.IOBase -- for IO constructor
{-# INLINE inlinePerformIO #-}
inlinePerformIO :: IO a -> a
inlinePerformIO (IO m) = case m realWorld# of (# _, r #) -> r
-- Now you can write things like this, which need IO action to define pure
-- functions:
data Seq = Seq !Int !(Ptr Base)
instance Eq Seq where
(==) (Seq (I# size1) (Ptr ptr1)) (Seq _ (Ptr ptr2)) = inlinePerformIO $ IO
(\s -> eqmem size1 ptr1 ptr2 s)
{-# INLINE eqmem #-}
eqmem remainingSize ptr1 ptr2 s = if remainingSize ==# 0# then (# s , True #)
else case readInt8OffAddr# ptr1 0# s of { (# s, i8a #) ->
case readInt8OffAddr# ptr2 0# s of { (# s, i8b #) ->
if i8a /=# i8b then (# s, False #)
else eqmem (remainingSize -# 1#) (plusAddr# ptr1 1#) (plusAddr#
ptr2 1#) s } }
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] A free monad theorem?
I'd like to know if the following reasoning can be made more precise: As we all know, the monadic bind operation has type: bind :: Monad m => m a -> (a -> m b) -> m b My intuition says that in order to apply the second argument to some non-trivial (i.e. non-bottom) value of type a, the bind operator needs to be able to somehow 'extract' a value (of type a) from the first argument (of type m a). I would like to argue that this is because bind is polymorphic in a, which makes it impossible to construct values of type a 'out of thin air' (besides bottom). Thus, however bind is defined, the only place where it can obtain a 'real' value of type a is from its first argument. Although one might think that this implies the existence of some function extract :: Monad m => m a -> a it is obvious that this is too limiting, as the IO monad plainly shows. Even monads that can be implemented in Haskell itself (the vast majority, it seems) usually need some additional (monad-specific) argument to their 'extract' (or 'run') function. However, even a value of type IO a /does/ produce a value of type a, only the 'value producing computation' is not a (pure) function. But how can all this be made more precise with less handwaiving? The background for my question is an argument I had some time ago with someone about what the 'real nature' of monads is. He argued that monads are mainly about 'chaining' (somehow wrapped up) values in an associative way, refering to the monad laws. I argued that monadic values get 'chained' in a very specific way and that in order to get an intuition about what this monadic chaining really means on the most general level, the standard model of 'computation that returns a value of type a' is the appropriate one. I tried to use the above (handwaving) argument to convince him (and myself) that this model is indeed 'the right one'. Furthermore, if it really is, then one might conjecture that for /every/ monad there must be some natural interpretation as the representation of some kind of computation (effectful or not). So my second question is: Are there known 'counter-examples' where this intuition breaks down, i.e. monads for which a computational interpretation is unknown or at least obscure enough not to qalify as 'natural'? Cheers, Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ReadP question
Tom Phoenix wrote:
On 8/30/06, Chris Kuklewicz <[EMAIL PROTECTED]> wrote:
> -- Simulate "(a?|b+|c*)*d" regular expression
But 'go' seems to not terminate with the leading 'star'
Unless I'm missing something... The part of the pattern inside the
parentheses should successfully match at least the empty string at the
beginning of the string. Since it's regulated by the second (outer)
'star', it will keep matching as long as it keeps succeeding; since it
keeps matching the empty string, it keeps matching forever in the same
spot.
To solve this problem, your implementation of 'star' could perhaps be
changed to answer "no more matches" rather than "infinitely many
matches" once the body fails to consume any characters.
Hope this helps!
--Tom Phoenix
And that is indeed the solution. But then I wanted $ end-of-line anchors (easy)
and ^ begin-of-line anchors (annoying). But it works now:
-- | Using ReadP to simulate regular expressions, finding the longest match
-- by Chris Kuklewicz, public domain
import Control.Monad
import Data.Set(Set,member)
import Data.Maybe(maybe)
import Text.ParserCombinators.ReadP
type R = Char -> ReadP (Int,Char)
dot :: R
dot _ = do x <- get
return (1,x)
anyOf :: Set Char -> R
anyOf s _ = do
x <- satisfy (`member` s)
return (1,x)
noneOf :: Set Char -> R
noneOf s _ = do
x <- satisfy (not.(`member` s))
return (1,x)
c :: Char -> R
c x _ = char x >> return (1,x)
cs :: String -> R
cs [] prev = return (0,prev)
cs xs _ = string xs >> return (length xs,last xs)
atBOL prev =
case prev of '\n' -> return (0,prev)
_ -> pfail
atEOL prev = do
rest <- look
case rest of [] -> return (0,prev)
('\n':_) -> return (0,prev)
_ -> pfail
-- Consume like x? x+ x* and return the length
quest,plus,star :: R -> R
quest x = x <|> (\prev -> return (0,prev))
plus x = x +> star x
star x prev = until0 0 prev
where until0 t prev' = do
(len,prev'') <- quest x prev'
if (0==len)
then return (t,prev'')
else let tot = t + len
in seq tot (until0 tot prev'')
upToN :: Int -> R -> R
upToN n x = helper n
where helper 0 prev t = return (t,prev)
helper i prev t = do
(len,prev') <- x prev
if 0==len
then return (t,prev')
else helper (pred i) prev' $! t+len
ranged 0 Nothing x = star x
ranged 0 (Just n) x | n>0 = upToN n x
ranged m n x | (m>=0) && maybe True (\n'->n'>=m) n =
doSeq (replicate m x) +> (ranged 0 (fmap (subtract m) n) x)
| otherwise = (\prev -> return (0,prev))
infixr 6 +>
infixr 5 <|>
(+>),(<|>) :: R -> R -> R
(+>) x y = (\prev -> do
(lenX,prev') <- x prev
(lenY,prev'') <- y prev'
let tot = lenX + lenY
seq tot (return (tot,prev''))
)
(<|>) x y = (\prev -> (x prev) +++ (y prev))
orSeq,doSeq :: [R] -> R
orSeq [] prev = return (0,prev)
orSeq xs prev = foldr1 (<|>) xs $ prev
doSeq [] prev = return (0,prev)
doSeq xs prev = foldr1 (+>) xs $ prev
-- Simulate "(^a|b+|c*|^.)*(d|_rest_)$" regular expression
test = star (orSeq [quest (c 'a')
,plus (c 'b')
,star (c 'c')
,atBOL +> dot ]) +> doSeq [c 'd' <|> cs "_rest_",atEOL]
go foo = case readP_to_S (gather (test '\n')) foo of
[] -> Nothing
xs -> Just (last xs)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] monads once again: a newbie perspective
Il Thu, Aug 31, 2006 at 02:39:59PM +0100, Simon Peyton-Jones ebbe a scrivere: > Andrea > > Don't forget to link to it from here! > http://haskell.org/haskellwiki/Books_and_tutorials#Using_monads Simon, I'll do. But now the text is far from being complete: there's only the code... (the most difficult part, for me at least!). Thanks for your kind attention. Andrea ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell for hp-ux (ia64)
Does anyone know of a binary for hp-ux (ia64)? I have permission from my company to try and go forward with using Haskell for development with my team. But, we are running hp-ux on a 16 processor(ia64) box and I can’t find a build for it. B Green * The information contained in this communication is confidential, is intended only for the use of the recipient named above, and may be legally privileged. If the reader of this message is not the intended recipient, you are hereby notified that any dissemination, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please resend this communication to the sender and delete the original message or any copy of it from your computer system. Thank you. * ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: data structures question
On Thursday 31 August 2006 09:09, Bulat Ziganshin wrote: > Hello Benjamin, > > Wednesday, August 30, 2006, 11:40:09 PM, you wrote: > > Matthias Fischmann wrote: > >> The trick is that Int is not the only index data type, but tuples > >> of > >> > >> index data types are, too. Do this: > >> | type Point = (State, State, Int) > >> | type TypeV = Array State Double > >> | > >> | matrix :: TypeV > >> | matrix = array bounds values > >> |where > >> |... > > > > Surely you meant to say > > > > | type TypeV = Array Point Double > > which will require 128 gigs of memory for 32-bit cpus and even > slightly more for 64-bit ones :) Wow, that's bad. But then the situiation isn't really much better with a simple Array Int Double, values of which would always use up all my memory. Surely you don't mean that ;) Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] source code for haskell web server?
On Wed, 30 Aug 2006, Tim Newsham wrote: > > Does anyone know where I could find the source code for the Haskell web > > server described in the papers "Tackling the Awkward Squad" by SPJ and > > "Writing High-Performance Server Applications in Haskell, Case Study: A > > Haskell Web Server" by Simon Marlow? > > I dug up an old copy of hws from the haskell CVS and a copy of hws-wp > from an old CVSweb and got both to build on modern ghc. I'm using > HWS as my server and have a small page with the sources which include > my patches: > > http://www.thenewsh.com/~hws/ > > Feel free to contact me with questions or suggestions. Btw. would it be possible and sensible to use the same Response and Request data structures both for the client module Network.HTTP and the Haskell Web Server? It would simplify forwarding of requests and responses. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] state and exception or types again...
Il Wed, Aug 30, 2006 at 11:24:45AM +0100, Brian Hulley ebbe a scrivere:
> Thanks, glad to be of help.
I met Haskell a couple of months ago, when I switched my window
manager to Ion. Tuomo Valkonen, its developer, uses darcs. Moreover he
develops a small PIM, riot, written in Haskell. I wanted to play
around with it but the source code was literally unreadable, for me. I
could not understand a single line.
I do some php. Lately I discovered Javascript and Lua, and I fell in
love with their object-oriented capabilities. I'm not a real coder
(though I develop a wiki in php), but I like getting to know new
programming practices. I've been intrigue with functional programming
for quite sometime but I just knew a bit of Scheme, because it's used
as a scripting language in LilyPond (a package for writing music
sheets).
So I decided to spend my August holidays to study Haskell. I started
reading some tutorial but could not understand what was going on. I
then thought to take the long way: I watched the Abelson and Sussman's
lectures and used ghci to (sort of) follow what they were doing.
Coming from dynamic typed languages (I know very little C) the type
system was horrible. Monads seemed mysterious objects.
I've read in the "Yet Another..." that the Haskell community is very
supportive.
With your help I have now a different perspective. Playing with
Haskell is like completing a puzzle, whose pieces' shapes are made up
with rules that, at first, you seem not be able to grasp.
You keep pushing the last piece, and it just doesn't fit in.
Then you realize that shapes are actually types. And when you start
understanding the rules of type construction and type matching, now
you can recognize the shapes of the pieces you are playing with. And
start making rational guesses on where they should go.
Now, when I see "Compiling ... Ok, modules loaded: " I feel like I
ended up solving the puzzle.
It's an amazing pleasure... Haskell and functional programming.
Without you I couldn't do it. Thank you so much!
The tutorial will have this outline: first we build a monad adding
output, exception, and state. Then we use monad transformer to take
out state and output and add debug, doing lifting, put(ing) and
get(ing) by hand, to understand the central role of type
matching/construction.
We end up with the following code, that should clearly show all the
previous (hand made) steps should lead. No lambda calculus inhere!
Once again, thanks!
Andrea
-The Final Evaluator
module MyStateT where
import Control.Monad.State hiding (State)
data Term = Con Int
| Add Term Term
deriving (Show)
type IOStack = [Output]
type Output = String
type Debug = [String]
data EvalST = State {getIOS :: IOStack, getDebug :: Debug, getCount:: Int}
deriving(Show)
type Exception = String
data MT a = Fail Exception
| Done {unpackDone :: a }
deriving (Show)
type Eval s a = StateT s MT a
instance Monad MT where
return a = Done a
m >>= f = case m of
Fail e -> Fail e
Done a -> f a
instance Functor MT where
fmap _ (Fail a) = Fail a
fmap f (Done a) = Done (f a)
emptyState = State [] [] 0
stopExecT exc = lift $ Fail exc
catchT e = do st <- get
let s = getCount st
let es = getDebug st
let o = getIOS st
let exc = "Debug msg at Iteration " ++ show s ++ ": " ++ e
put $ State o (exc:es) s
printT :: Output -> Eval EvalST ()
printT o = do st <- get
let s = getCount st
let e = getDebug st
let os = getIOS st
let out = show s ++ " - " ++ o
put $ State (out:os) e s
incTcounter :: Eval EvalST ()
incTcounter = do st <- get
let s = getCount st
let e = getDebug st
let o = getIOS st
put $ State o e (s+1)
evalT :: Term -> Eval EvalST Int
evalT (Con a) = do incTcounter
printT (formatLine (Con a) a)
return a
evalT (Add t u) = do a <- evalT t
b <- evalT u
incTcounter
let out = formatLine (Add t u) (a + b)
printT out
case (a+b) of
42 -> do catchT "The Ultimate Answer Has Been Computed!!
Now I'm tired!"
return (a+b)
11 -> stopExecT "11 I do not like this number!"
otherwise -> return (a + b)
formatLine :: Term -> Int -> Output
formatLine t a = "eval (" ++ show t ++ ") <= " ++ show a
printAll :: [String] -> IO ()
printAll [] = return ()
printAll (a:xs) = do print a
printAll xs
eval :: Term -> IO ()
eval exp = case execStateT (evalT exp) emptyState of
Fail e -> print e
Done (State a b c )
-> d
Re: [Haskell-cafe] Re: data structures question
Hello Benjamin, Wednesday, August 30, 2006, 11:40:09 PM, you wrote: > Matthias Fischmann wrote: >> The trick is that Int is not the only index data type, but tuples of >> index data types are, too. Do this: >> >> | type Point = (State, State, Int) >> | type TypeV = Array State Double >> | >> | matrix :: TypeV >> | matrix = array bounds values >> |where >> |... > Surely you meant to say > | type TypeV = Array Point Double which will require 128 gigs of memory for 32-bit cpus and even slightly more for 64-bit ones :) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ReadP question
Chris Kuklewicz wrote: > I just tried to mimic regular expression matching with ReadP and got what > seems like a non-terminating program. Is there another way to use ReadP to > do this? > > >-- Simulate "(a?|b+|c*)*d" regular expression > >test = star (choice [quest (c 'a') > >,plus (c 'b') > >,star (c 'c')]) +> c 'd' Indeed, this cannot work. ReadP delivers parses in order of increasing length, and your expression produces infinitely many parses of the empty string, you never get to the interesting matches. I'd say, the best solution is to use an equivalent regex which does not contain something of the form 'many (return x)': > >-- Simulate "(a?|b+|c*)*d" regular expression > >test' = star (choice [(c 'a') > > ,plus (c 'b') > > ,plus (c 'c')]) +> c 'd' Udo. -- f u cn rd ths, u cn gt a gd jb n cmptr prgrmmng. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
