next_permutation being a subroutine in the C++ standard library that gives 
you the lexographically next permutation of an array.

http://wordaligned.org/articles/next-permutation?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+wordaligned+(Word+Aligned)

Interesting. :-)

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

Darren New wrote:

> Interesting. :-)

"while (!(*i < *--j)) {}"

Um, yeah, "interesting" would be the term I'd use. WTF? o_O



Personally, I'd do it this way:

nextP :: Ord x => [x] -> Maybe [x]
nextP []  = Nothing
nextP [x] = Nothing
nextP xs  =
   case split (reverse xs) of
     ([] , _  ) -> Nothing
     (ss', ps') ->
       let
         p0         = head ps'
         (ss0, ss1) = span (p0 >=) ss'
         s0         = head ss1
         ps         = reverse (s0 : tail ps')
         ss         = ss0 ++ [p0] ++ tail ss1
       in Just (ps ++ ss)

split :: Ord x => [x] -> ([x], [x])
split [] = ([], [])
split (x:xs) = work x xs
   where
     work x0 [] = ([x0], [])
     work x0 (x:xs)
       | x >= x0   = let (ys,zs) = work x xs in (x0:ys, zs)
       | otherwise = ([x0], x:xs)

Post a reply to this message

Invisible wrote:
> "while (!(*i < *--j)) {}"

C has always advocated piling up a bunch of side effects inside 
conditionals.   Even to the point where Google's go has completely useless 
syntax for doing so.

In go, you can write
   if x := y + 1; x > 5 { ... }

Which is always exactly precisely the same as
   x := y + 1;
   if x > 5 { ... }

Since you *always* need braces, and the result of evaluating the assignment 
isn't ever used as the conditional, it's just a way of embedding 
side-effects into a part of a statement that should be side-effect free, 
apparently because the people designing go are so used to C's actually 
*useful* side effects that they missed the result.

The above line could also be
   do { j -= 1; } while (*j <= *i);
(or maybe while *i < *j. I don't care to work it out for sure)

So, yeah, it's opaque C++ code there.


> Um, yeah, "interesting" would be the term I'd use. WTF? o_O

The algorithm is interesting, not the implementation.

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Invisible wrote:
> > "while (!(*i < *--j)) {}"

> C has always advocated piling up a bunch of side effects inside 
> conditionals.

  OTOH, once you learn to read it, it's not that bad.

  It's a bit like using "++i" instead of "i = i + 1". The latter might be
clearer at first, but once you understand what "++i" means, not really.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Invisible wrote:
>>> "while (!(*i < *--j)) {}"
> 
>> C has always advocated piling up a bunch of side effects inside 
>> conditionals.
> 
>   OTOH, once you learn to read it, it's not that bad.

Not in moderation. If something in the condition can't easily be expressed 
outside the condition, it's helpful. For example,
   while (EOF != (c = getchar())) { ... }
You can't really put the assignment outside the condition without 
duplicating that code, and it's kind of an accident of the design of the 
libraries that means you can't find out the result from getchar without 
invoking undesirable side-effect.[1] But convolving the comparison and the 
decrement in this case was unnecessary, I think. Doing the decrement in the 
body would say "keep decrementing until the condition is satisfied", which 
doesn't really come across in the way it's written.

>   It's a bit like using "++i" instead of "i = i + 1". The latter might be
> clearer at first, but once you understand what "++i" means, not really.

You definitely have to look at that expression to figure out what it's 
doing. Of course, they could have reversed the letters and made it a little 
clearer, too.


[1] You don't have this problem with iterators, for example, as you can just 
as for "*j" as often as you want without changing "j".  Eiffel and Ada solve 
it by requiring/suggesting that anything that has side effects doesn't 
return a value. So in Eiffel, there's a (void) procedure to read the next 
character into a buffer inside the object, and a function to get whatever 
character was most recently read, so you don't need to do the assignment 
inside the condition to save the character it returned, the way you need to 
in non-OO C.

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

>     ([] , _  ) -> Nothing

Yeh, it's really clear what this line does to a non-Haskeller :-)

Post a reply to this message

scott wrote:
>>     ([] , _  ) -> Nothing
> 
> Yeh, it's really clear what this line does to a non-Haskeller :-)

I'll tell you what it does: It makes the function crash. o_O

It *should* in fact be

    (_  , [] ) -> Nothing

It seems I got my arguments the wrong way around. :-/

As for what it *means*, it means that if the prefix is empty ("[]"), 
there is no next permutation ("Nothing"). The "_" simply means that it 
doesn't matter what the suffix part is.

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> scott wrote:
> >>     ([] , _  ) -> Nothing
> > 
> > Yeh, it's really clear what this line does to a non-Haskeller :-)

> I'll tell you what it does: It makes the function crash. o_O

  After this you should really stop picking on C variants (or at the very
least, not immediately compare them to Haskell). ;)

-- 
                                                          - Warp

Post a reply to this message

>>>>     ([] , _  ) -> Nothing
>>> Yeh, it's really clear what this line does to a non-Haskeller :-)
> 
>> I'll tell you what it does: It makes the function crash. o_O
> 
>   After this you should really stop picking on C variants (or at the very
> least, not immediately compare them to Haskell). ;)

Why? Because I wrote some code with a small typo?

Post a reply to this message

scott wrote:
>>     ([] , _  ) -> Nothing
> 
> Yeh, it's really clear what this line does to a non-Haskeller :-)

It's pretty standard notation for functional languages. Erlang uses the same 
notation. If you get a two-element tuple with the first element being an 
empty list, the result is an arbitrary atomic value (not unlike an "enum") 
called "Nothing".

It's no less clear than function calls or array indexes if you've ever used 
that operation before in a programming language. It's about as complex as a 
case statement.

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

Darren New wrote:

> It's about as complex as a case statement.

In particular, it *is* [part of] a case expression. ;-)

Post a reply to this message

Invisible wrote:
> Darren New wrote:
>> It's about as complex as a case statement.
> In particular, it *is* [part of] a case expression. ;-)

Yes, *I* know that. :-)

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> >>>>     ([] , _  ) -> Nothing
> >>> Yeh, it's really clear what this line does to a non-Haskeller :-)
> > 
> >> I'll tell you what it does: It makes the function crash. o_O
> > 
> >   After this you should really stop picking on C variants (or at the very
> > least, not immediately compare them to Haskell). ;)

> Why? Because I wrote some code with a small typo?

  Because it's exactly as (or even more) obfuscated as your hated C, and
it seems to be equally easy to make something "crash" by mistake.

  Also you should understand that the Haskell line might not be obfuscated
to *you* because you know how to read it, but it's quite obfuscated to
others who don't understand it. The same works for C as well. Thus you
really don't prove anything by saying "that piece of C(++) is really
obfuscated, I don't understand it, here's how I would write it in Haskell"
and proceed to present a program which is at least as obfuscated.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   Because it's exactly as (or even more) obfuscated as your hated C, and
> it seems to be equally easy to make something "crash" by mistake.

If you make a typo in a Haskell program, the program stops and says 
"error: you tried to access the first element of an empty list". If you 
make a typo in a C program, the program stops and says "error: 
segmantation fault".

The former is easier to debug [although, admittedly, it gives you 
absolutely no indication of *where* the program crashed], while the 
latter is no fun at all. Also, the former is an *exception*. You can 
catch exceptions and handle them if you want. As far as I'm aware, you 
cannot catch segfaults.

>   Also you should understand that the Haskell line might not be obfuscated
> to *you* because you know how to read it, but it's quite obfuscated to
> others who don't understand it. The same works for C as well. Thus you
> really don't prove anything by saying "that piece of C(++) is really
> obfuscated, I don't understand it, here's how I would write it in Haskell"
> and proceed to present a program which is at least as obfuscated.

Performing multiple steps all at once in a small blob of symbols? Sounds 
fairly non-trivial to me. By contrast, the Haskell version doesn't use 
any remotely advanced features of Haskell, just a few case expressions 
with some basic pattern matching. No monads, no typeclasses, no 
existential types, nothing. Just plain ordinary pattern matching.

For me, the question is not how obscure it looks, but how difficult it 
is to explain it.

FWIW, I think this particular algorithm itself is pretty tricky, no 
matter which language you use for it.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Warp wrote:

> >   Because it's exactly as (or even more) obfuscated as your hated C, and
> > it seems to be equally easy to make something "crash" by mistake.

> If you make a typo in a Haskell program, the program stops and says 
> "error: you tried to access the first element of an empty list". If you 
> make a typo in a C program, the program stops and says "error: 
> segmantation fault".

  And?

> The former is easier to debug [although, admittedly, it gives you 
> absolutely no indication of *where* the program crashed], while the 
> latter is no fun at all. Also, the former is an *exception*. You can 
> catch exceptions and handle them if you want. As far as I'm aware, you 
> cannot catch segfaults.

  Actually you can catch exceptions in most systems, and you can resolve
the exact location of the crash using a debugger.

> >   Also you should understand that the Haskell line might not be obfuscated
> > to *you* because you know how to read it, but it's quite obfuscated to
> > others who don't understand it. The same works for C as well. Thus you
> > really don't prove anything by saying "that piece of C(++) is really
> > obfuscated, I don't understand it, here's how I would write it in Haskell"
> > and proceed to present a program which is at least as obfuscated.

> Performing multiple steps all at once in a small blob of symbols? Sounds 
> fairly non-trivial to me.

  Haskell is fairly (in)famous for its one-liners which do tons of things.

> By contrast, the Haskell version doesn't use 
> any remotely advanced features of Haskell, just a few case expressions 
> with some basic pattern matching. No monads, no typeclasses, no 
> existential types, nothing. Just plain ordinary pattern matching.

  Because you wrote it so. The C++ version could also have been written to
be as verbose and straightforward as possible. It's not like you *have* to
write dense code.

> For me, the question is not how obscure it looks, but how difficult it 
> is to explain it.

  Many Haskell one-liners would probably take entire books to explain.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v8 wrote:
> make a typo in a C program, the program stops and says "error: 
> segmantation fault".

*If* you're lucky.  What's worse is when it *doesn't*. :-)

> As far as I'm aware, you cannot catch segfaults.

You can, but not in a portable way, a language-defined way, or in a way 
that's useful for debugging or continuing on.  You cannot, for example, 
catch a segfault and use it to extend the size of the array you just ran off 
the end of.

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

Warp wrote:
>   Haskell is fairly (in)famous for its one-liners which do tons of things.

I think APL (and now J) is the canonical example for that.

>   Because you wrote it so. 

Well, the particular bit you complained about is no more complex than
    case 23: return 0;
in C. It's just that Haskell has literals that aren't in C, so "case 23" 
looks funky.

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

>> make a typo in a C program, the program stops and says "error: 
>> segmantation fault".
> 
> *If* you're lucky.  What's worse is when it *doesn't*. :-)

Worse Than Failure.

>> As far as I'm aware, you cannot catch segfaults.
> 
> You can, but not in a portable way.

I had a feeling the OS might provide a way to do this. (Presumably 
that's how the shell tells you your program segfaulted.) And that would 
make it OS-dependent...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

>> If you make a typo in a Haskell program, the program stops and says 
>> "error: you tried to access the first element of an empty list". If you 
>> make a typo in a C program, the program stops and says "error: 
>> segmantation fault".
> 
>   And?

And if your program stops with an exception, you can catch and handle 
it. If it segaults, AFAIK you can't do anything about it.

>   Actually you can catch exceptions in most systems, and you can resolve
> the exact location of the crash using a debugger.

C and C++ have debuggers which are actually useable. I'll give you that one.

>> By contrast, the Haskell version doesn't use 
>> any remotely advanced features of Haskell, just a few case expressions 
>> with some basic pattern matching. No monads, no typeclasses, no 
>> existential types, nothing. Just plain ordinary pattern matching.
> 
>   Because you wrote it so. The C++ version could also have been written to
> be as verbose and straightforward as possible. It's not like you *have* to
> write dense code.

No, BUT EVERYBODY DOES.

Nobody told this C++ programmer "hey, please write this in the most 
complicated way possible". He just did, out of habit.

Personally, I don't have a problem with being able to incriment or 
decriment a variable just by saying "x++" or whatever. It's a nice 
shortcut. But when you reach the point of performing an assignment and 
incriment at the same time... well, *I* certainly wouldn't write code 
like that. I'd be forever having to double-check whether the incriment 
happens before or after the assignment, and so on.

>> For me, the question is not how obscure it looks, but how difficult it 
>> is to explain it.
> 
>   Many Haskell one-liners would probably take entire books to explain.

Haskell allows you to do clever and rather opaque things such as compute 
a list of all the prime numbers in the universe in a one-liner, or 
Pascal's triangle, or the Fibonacci numbers, or whatever. And, yes, it 
takes some explaining to unravel.

*This* program, however, involves no such cleverness. Merely a few case 
expressions. Aside from the unfamiliar syntax, there's really little 
about it that's complex. No fancy tricks, no clever math, just a few 
conditional tests and a couple of function calls.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Orchid XP v8 wrote:
> > make a typo in a C program, the program stops and says "error: 
> > segmantation fault".

> *If* you're lucky.  What's worse is when it *doesn't*. :-)

  You seriously claiming that if you make a typo in Haskell, it always
magically knows that and gives you an error message?

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   You seriously claiming that if you make a typo in Haskell, it always
> magically knows that and gives you an error message?

What's magic?

If you type something wrong, it might be a syntax error. (Any 
half-decent compiler will catch these.) If you type the wrong name by 
mistake, it's probably a type error. If you assume that a certain list 
will always contain 3 items (for example) and actually it doesn't, 
you'll get an exception when you try to access a non-existent element.

It's not *guaranteed* that all mistakes will be caught. If you 
accidentally write "x + x" instead of "x + y", no error (just the wrong 
result). Same as any other language.

Let's look at this the other way around: There is no typo you can 
possibly make which will result in a segfault. (Unless you're doing 
something *very* special, like calling an external C routine or 
something.) About the worst that can happen is that your program eats 
craploads of RAM or goes into an infinite loop. (Or, if you're using 
explicit concurrency with locks, you might deadlock or something.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> C and C++ have debuggers which are actually useable. I'll give you that 
> one.

Because they need it, because when something goes wrong you have to step 
outside the language into a different address space to be able to figure out 
why. ;-)

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Orchid XP v8 wrote:
>>> make a typo in a C program, the program stops and says "error: 
>>> segmantation fault".
> 
>> *If* you're lucky.  What's worse is when it *doesn't*. :-)
> 
>   You seriously claiming that if you make a typo in Haskell, it always
> magically knows that and gives you an error message?

Me? No.

I'm saying you're lucky if when you make a mistake in C you get a segfault. 
If you're unlucky, you clobber some random unrelated variable that *is* 
allocated and things progress as normal except with totally undefined results.

If you make a mistake in Haskell such that the results are undefined, it 
stops in a way that's probably pretty easy to debug compared to a segfault in C.

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Orchid XP v8 wrote:
> > C and C++ have debuggers which are actually useable. I'll give you that 
> > one.

> Because they need it, because when something goes wrong you have to step 
> outside the language into a different address space to be able to figure out 
> why. ;-)

  Can you name one language which would not benefit from a debugger (which
you can use, among other things, to insert breakpoints, execute the program
step-by-step and examine the values of all objects at current scope)?

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   Can you name one language which would not benefit from a debugger (which
> you can use, among other things, to insert breakpoints, execute the program
> step-by-step and examine the values of all objects at current scope)?

I know *I* would like it better if Haskell had a quality debugger.

They say if a Haskell program compiles, it usually works correctly. This 
is true, but note that the phrase is "usually".

(There *is* a debug feature in recent versions of GHC, but it doesn't 
seem to work terribly well. And crawling through a complicated piece of 
program using a CLI interface isn't much fun anyway...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Warp wrote:
>   Can you name one language which would not benefit from a debugger (which
> you can use, among other things, to insert breakpoints, execute the program
> step-by-step and examine the values of all objects at current scope)?

No language per se, but environments. :-)

I just try to avoid languages where the primary debugging tools are outside 
the language. (Altho APL is cool, I can't imagine doing a production program 
in a language that needs something like OBSERVE[1], for example.)

I was pretty impressed at how VS lets you put breakpoints in code-behind 
pages so you can single-step a piece of code as it processes a web request, 
which is really a PITA in most of the other web-oriented languages like PHP.

So yeah, of course debuggers are *useful*. Do I want an external program to 
be the *only* way to track down bugs? Nah.  C is useful too. That doesn't 
mean I want C to be the only language I can use.



[1] Since Google is making it hard to find, the "observe" command sets a 
flag that makes each APL statement print the line it's running, puts a 
carret under the current operator it's evaluating, prints out both 
arguments, and then the result, essentially single-stepping the evaluation 
of a single expression with copious output.

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

>>>     ([] , _  ) -> Nothing
>>
>> Yeh, it's really clear what this line does to a non-Haskeller :-)
>
> It's pretty standard notation for functional languages. Erlang uses the 
> same notation. If you get a two-element tuple with the first element being 
> an empty list, the result is an arbitrary atomic value (not unlike an 
> "enum") called "Nothing".

Sure, I didn't doubt there was a pretty easy explanation behind it, it's 
just [], _ and the whole statement syntax had no meaning to me before it was 
explained.  I would imagine once Andrew knew what -- and * does in C (I 
think < and ! are common enough not to need to explain?) he would know what 
the statement he highlighted meant too.  I don't see much difference.

Post a reply to this message

scott wrote:

> Sure, I didn't doubt there was a pretty easy explanation behind it, it's 
> just [], _ and the whole statement syntax had no meaning to me before it 
> was explained.  I would imagine once Andrew knew what -- and * does in C 
> (I think < and ! are common enough not to need to explain?) he would 
> know what the statement he highlighted meant too.  I don't see much 
> difference.

I *already* know that * is pointer dereference and -- is decriment. But 
now I have to sit here and wonder "is that pre-decriment or 
post-decriment? And in why is it 'not (x < y)" rather than 'x >= y'?" 
And similar questions. (Why "for (;;)" rather than "while true"? Is 
there some difference?)

(Also... I just noticed how many one-letter variable names there are. So 
much for that being a bad thing.)

Post a reply to this message

> I *already* know that * is pointer dereference and -- is decriment. But 
> now I have to sit here and wonder "is that pre-decriment or 
> post-decriment?

Like I have to sit and wonder why it's (suffix,prefix) and not 
(prefix,suffix) in your example?

> And in why is it 'not (x < y)" rather than 'x >= y'?"

Aren't they the same? (btw the only reason I can see that you would use the 
first one is if the types being used don't have the >= operator defined). 
IIRC quite a lot of functions and libraries only assume that one of those 
operators is implemented, so that's probably why you'll see stuff like that.

> And similar questions. (Why "for (;;)" rather than "while true"? Is there 
> some difference?)

Not that I'm aware of.

Post a reply to this message

>> I *already* know that * is pointer dereference and -- is decriment. 
>> But now I have to sit here and wonder "is that pre-decriment or 
>> post-decriment?
> 
> Like I have to sit and wonder why it's (suffix,prefix) and not 
> (prefix,suffix) in your example?

No specific reason. I probably did it that way around because "split" 
takes the list in reverse order. (Working from the back towards the 
front is inefficient for a single-linked list, so I reversed the list so 
it can be processed from front to back instead.) Technically you could 
return the sublists either way around if you wanted. I just did it this 
way because if you take (x, y) and do x ++ y, you get the original 
(backwards) list. If you'd returned the components the other way around, 
you'd have to do y ++ x instead.

>> And in why is it 'not (x < y)" rather than 'x >= y'?"
> 
> Aren't they the same?

You'd certainly think so.

> (btw the only reason I can see that you would use 
> the first one is if the types being used don't have the >= operator 
> defined). IIRC quite a lot of functions and libraries only assume that 
> one of those operators is implemented, so that's probably why you'll see 
> stuff like that.

Hmm, I see.

Of course, we're working with *digits* here, for which both operators 
are definitely defined. However, it seems this part of the code is from 
a library, so presumably it's supposed to work with anything.

(In Haskell, it is impossible to define one ordering relation without 
also defining the others. Well, no, not impossible, but you'd have to 
purposely go out of your way to do it. So in Haskell it's not something 
a library needs to worry about it. But now I recall that in C++, these 
are all seperate, notionally unrelated operators.)

>> And similar questions. (Why "for (;;)" rather than "while true"? Is 
>> there some difference?)
> 
> Not that I'm aware of.

It's like when a Haskell programmer writes a new function that's 
equivilent to an existing one. You have to sit there and wonder why they 
did that. Was it personal taste, or is there actually some subtle 
difference you've missed?

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> > And in why is it 'not (x < y)" rather than 'x >= y'?"

> Aren't they the same? (btw the only reason I can see that you would use the 
> first one is if the types being used don't have the >= operator defined). 
> IIRC quite a lot of functions and libraries only assume that one of those 
> operators is implemented, so that's probably why you'll see stuff like that.

  It is customary in the C++ standard library to demand as little as
possible from the types being handled. Anything requiring comparison of
element usually demands only operator< from the elements (if the algorithm
can be feasibly be implemented using that operator only).

  If you are making a generic algorithm or data container which compares
elements, it's also usually a good idea to demand as little as possible
from it, and stick to operator< exclusively, if possible.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> from it, and stick to operator< exclusively, if possible.

And other than readability, compilers these days are smart enough to 
generate the same optimal[1] code for it regardless.

[1] Funny how "optimized" no longer means what it used to, isn't it?

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message