Re: [Haskell-cafe] abs minBound < (0 :: Int) && negate minBound == (minBound :: Int)

[Kyle Miller]

On Sun, Aug 18, 2013 at 8:04 PM, Richard A. O'Keefe wrote:

> The argument for twos-complement, which always puzzled me, is that the
> other
> systems have two ways to represent zero.  I never found this to be a
> problem,
> not even for bitwise operations, on the B6700.  I *did* find "abs x < 0"
> succeeding to be a pain in the posterior.  (The B6700 had two different
> tests:
> 'are these two numbers equal' and 'are these two bit patterns equal'.)


I think a better argument for twos complement is that you're just doing all
of your computations modulo 2^n (where n is 32 or 64 or whatever), and
addition and multiplication work as expected modulo anything.  The idea of
negative and positive in a system like this is artificial, though.  The
standard convention follows from the observation that 0-1 should be -1, and
if you use the hardware that is for positive numbers, and assume that you
can always carry another 1 for the highest order bit, then 0-1 is
...111.  It's not that 2^n - 1 is actually -1, but that it acts like a
-1 would act.  It's only by convention that numbers which begin with a 1
are considered to be negative (that, and Intel has special hardware for
detecting if a number has its leading 1 set).

However, we could adopt the convention that you need two leading ones to
make a negative number, and everything would work out, except for the
inequality testing built into the CPU.  This would give us a lot more
positive numbers, and then abs wouldn't have this problem :-)

Or, three other options: 1) make MIN_INT outside the domain of abs, 2) make
the range of abs be some unsigned int type, or 3) use Integer (i.e., use a
type which actually represents integers rather than a type which can only
handle small integers).

Kyle
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Parsec question

[Kyle Miller]

Because of laziness, you do in a sense only take the first successful
value.  When I've made parser combinators for Python before, I've used
either generators or exceptions to get lazy evaluation, since computing the
whole list of possibilities for each bind would ruin the running time of
the algorithm (or make it never terminate).  From your go code, it looks
like you're evaluating the entire list.

The bind you give looks like it's for a backtracking parser.  For
non-backtracking, though, I believe it would be possible to use Maybe.
 Parsec has a different bind operator which only lets backtracking happen
when you explicitly allow it with 'try'.

Assuming you're wanting a full backtracking parser, here's a counterexample
for the "take 1":

needsList = do
  v <- many (char 'a')
  a <- return v  -- just to make sure the "take 1" bind happens at least
once before the next step
  guard $ length a == 3
  return a

If my input string is "", then many (char 'a') will produce matches of
'', 'a', 'aa', 'aaa', and '', but the bind will probably force the
incorrect one of these before it reaches the guard.

I can't guarantee this is any good, and I haven't looked at it in a while,
but at [1] I have an example of using exceptions to get a parsec-like
backtracking-when-explicitly-allowed parser.  I was planning on writing an
article about how to do this technique, but I never got around to it.

Kyle

[1] https://github.com/kmill/metaview/blob/master/src/mparserlib/parser.py


On Wed, Jul 24, 2013 at 10:26 AM, C K Kashyap  wrote:

> Dear Cafe,
>
> I am trying to implement[1] parsec in go using the "Monadic Parser
> Combinators" paper [2] . I've been able to implement "plus" "bind" and
> "many"
> While doing the implementation - I looked at bind closely
>
> bind :: Parser a -> (a -> Parser b) -> Parser b
> p `bind` f = \inp -> concat [f v inp' | (v,inp') <- p inp]
>
> I wondered if the result needs the complete list - wouldn't just the first
> successful value suffice?
> Perhaps -
> p `bind` f = \inp -> take 1 $ concat [f v inp' | (v,inp') <- p inp]
>
> Will this miss out matches?
>
>
> Regards,
> Kashyap
>
> [1] https://github.com/ckkashyap/parsec/blob/master/parsec.go
> [2] Monadic Parser Combinators: Graham Hutton, Erik Meijer
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe