« first day (345 days earlier)      last day (4605 days later) » 

10:00 PM
@FredOverflow fix gives a fixed-point of a function. And it just uses the math definition directly: let x = f x.
 
fix :: (a -> a) -> a
fix f = let x = f x in x
 
When does that terminate?
let x = ... in x just doesn't make sense to me.
 
Recursive definition, which means first-class support.
It's not successive iterations.
 
@FredOverflow Usually let x = y in x is redundant and can be replaced with y. But in this case, you can't do that.
fix f = f x is missing the definition of x.
So, you define x as f x and you're done. Haskell magic handles the rest.
 
10:03 PM
I guess that's my problem, magic I don't understand.
 
Though I guess fix f = f (fix f) could work too (no GHC at hand here).
 
You cannot understand the recursive definition in terms of 'simpler' primitives.
You can find equivalent definitions that are similar in power but x = f x is a fundamental way to define a fixed-point.
 
so when a float can no long hold big numbers it pads it with 0? Why not just keep the last accurate precision?
 
So that's all there is.
 
Yep, fix f = f (fix f) works too: ideone.com/kzlgJ
 
10:06 PM
Okay, let's try with an example. If I say fix sin, I seem to get an endless loop. Why don't I get 0? :)
 
Maybe because sin is strict (I'm guessing, I don't know if that's true).
 
The fixed point of sin is 0, right?
 
(There can be more than one fixed point and none at all.)
 
I don't see how fix calculates a fix point. When I look at fix f = f (fix f), it just seems to apply f endlessly.
 
@FredOverflow Yes, 0 is a fixed-point of sin.
@FredOverflow Think lazy.
 
10:09 PM
@RMartinhoFernandes Please elaborate.
 
Lemme cook up an example (without sin).
fix (const 42) = (const 42) (fix (const 42))
No recursion is necessary.
 
And how does that calculate a fix point?
 
@FredOverflow (const 42) (fix (const 42)) evaluates to 42, without evaluating fix (const 42).
With sin you get fix sin = sin (fix sin), and that cannot be evaluated lazily.
 
Okay, and (const 42) x only yields x when x is 42... that seems a bit contrived. Is there a better, "real world" example?
 
fix id, which should be super easy also fails because id (fix id) needs to evaluate fix id.
 
10:16 PM
15
Q: How do I use fix, and how does it work?

Jason BakerI was a bit confused by the documentation for fix (although I think I understand what it's supposed to do now), so I looked at the source code. That left me more confused: fix :: (a -> a) -> a fix f = let x = f x in x How exactly does this return a fixed point? I decided to try it out ...

 
Ugh. I give up! >_<
It's probably easier to just ask the user how big his screen is.
 
If you pass a (a -> b) -> (a -> b) (the common usage of producing anonymous recursion), it always works.
 
is this a correct bubble sort algorithm?
	for(int i=0; i < SIZE ; i++)
		{
			for(int j=i+1;j < SIZE;j++)
			{
				if(numbers[i] > numbers[j])
				{
					temp = numbers[i];
					numbers[i] = numbers[j];
					numbers[j] = temp;
				}

			}
		}
 
> fix is a higher-order function which encodes the idea of recursion. [...] As you can see from the definition, fix is nothing more than this idea -- recursion encapsulated into a function.
Aha, so fix has nothing to do with what I understand as fix points.
@LewsTherin I think bubble sort only ever touches neighbors.
 
? Because the implementation on wikipedia looks different
@FredOverflow ?
 
10:20 PM
Well, first you start with mathematical fixed points, then you head into CS territory.
 
@FredOverflow It does find the fixed points of functions from functions to functions :)
 
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, it is not efficient for sorting large lists; other algorit...
> Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.
@RMartinhoFernandes Can you show me a practical application of fix?
 
@FredOverflow Take a single-line definition of factorial. factorial = fix (\f -> \x -> if x == 0 then 1 else f (x-1)).
 
@FredOverflow isn't that that how implemented it is doing?
 
so, how does one post multiline code in chat? Four leading spaces like on StackOverflow proper?
 
10:23 PM
@LewsTherin You have lots of (i, j) pairs that are not adjacent, so no.
 
Let's call fac' to fix (\f -> \x -> if x == 0 then 1 else f (x-1)). So, fac' = fac' (fix fac') = (\x -> if x == 0 then 1 else fac' (x-1))` which is the traditional definition.
@LewsTherin That's gnome sort. Or not.
 
@LewsTherin: Actually, I think the code you posted is a slow insertion-sort
 
@RMartinhoFernandes That function always spits out the value 1...
 
mmn ok
 
@LewsTherin
[EDITED]I can't figure out how to post code, and it's wrong anyways.
 
10:26 PM
@FredOverflow Ooops. ... x * f(x-1) :)
 
@MooingDuck That would be O(n), so it can't be right.
 
Sep 17 at 10:44, by sbi
If you are new here, please read the newbie hints. Thank you.
 
@MooingDuck that looks wrong
 
@FredOverflow: Correct. The code is totally wrong
 
@FredOverflow so I should only have one index variable ?
It looks adjacent to me
 
10:29 PM
@LewsTherin: Yeah, iterate from 0:SIZE-1, SIZE times.
 
@LewsTherin No it's not adjacent. When i == 0 && j == 4 is it adjacent?
Ok, what the heck is called the sorting algorithm whose loop invariant is "all elements before i are sorted and less than all elements after it"?
 
oops I see
 
Ha! Selection sort.
Gotta love those wikipedia sorting algorithm animations.
 
	int temp=0 ;
		for(int i=0; i < SIZE ; i++)
		{
			int k = i;
			for(int j=k+1;j < SIZE;j++)
			{
				if(numbers[k] > numbers[j])
				{
					temp = numbers[k];
					numbers[k] = numbers[j];
					numbers[j] = temp;
				}
				k++ ;
			}
		}
that correct?
 
@LewsTherin Seems so, but really, you could have just used j-1 instead of k.
:)
 
10:33 PM
@RMartinhoFernandes yeah I just chose the easy read lol
 
@LewsTherin Have you tested it?
 
@FredOverflow yeah it works
I'm using Java to write it...@FredOverflow thanks the book by Gosling is exactly what I want
 
@LewsTherin Does it work for the input [3, 2, 1]? I don't think it produces the correct result, but maybe I'm wrong.
@LewsTherin glad to hear it
 
@FredOverflow nope you are right :(
 
Your inner for loop is wrong. You go from "somewhere in the middle" to the end, but you should go from the start to "somewhere in the middle" instead.
You always have to start the inner loop by looking at the first element, but you only do that in your first outer iteration.
When the inner loop has completed for the first time, what can you say about the list?
 
10:39 PM
@FredOverflow I see your point
 
For example, [3, 2, 1] will be changed to [2, 1, 3]. What do you observe about the list?
 
It's different!
 
partially sorted? Stops midpoint or something
 
So, a loop invariant of bubblesort is "the list is different from the previous iteration".
:P
 
the smallest value is not at the front.
 
10:42 PM
The point of bubble sort is that after one iteration, the largest element will always be at the very end of the list. So you never have to look at it anymore, and you can "shorten" the list to be sorted by one element after each iteration.
That is, after the second iteration, the 2nd largest element will be at the 2nd last position and so on.
 
	int temp=0 ;
		for(int i=0; i < SIZE ; i++)
		{
			for(int j=0;j < SIZE;j++)
			{
				if(j+1 < SIZE && numbers[j] > numbers[j+1])
				{
					temp = numbers[j+1];
					numbers[j+1] = numbers[j];
					numbers[j] = temp;
				}
			}
		}
 
That's why the inner loop keeps getting shorter at the end, not at the beginning.
j < SIZE is unnecessary work
 
@FredOverflow oh so I don't have to look at then end of the list..it is one iteration shorter
 
if(j+1 < SIZE is unnecessary work, just make sure j doesn't get too high with a proper loop condition.
 
dang...
 
10:45 PM
Also, your outer loop is going through SIZE iterations, but one less is sufficient. In a list of 10 elements, you only have to determine the 9 rightmost results. The last one will be correct by definition (there is no other place it could go to, anyway).
 
I have no idea how to do it without j+1 < SIZE can't think
for(int i=0; i < SIZE-i ; i++)
		{
			for(int j=0;j < SIZE-i;j++)
			{
				if(j+1 < SIZE-i && numbers[j] > numbers[j+1])
				{
					temp = numbers[j+1];
					numbers[j+1] = numbers[j];
					numbers[j] = temp;
				}
			}
		}
 
for(int i=0; i < SIZE-i ; i++) doesn't make any sense.
 
Why not?
 
That will make only half as many iterations as needed.
With 10 elements, you need 9 outer iterations, not 5.
That should probably be SIZE-1 instead of SIZE-i.
 
It shouldn't make half the iterations...
SIZE - i should be SIZE
at first
 
10:50 PM
The loop condition is evaluated freshly after each iteration.
So when i is 5, you will evaluate 5 < 10 - 5 and the loop will stop.
But i needs to go up to 9.
 
Oh yeah...damn it..Bubble sort is supposed to be easy :(
 
Now for the other problem. Your inner loop condition is j < SIZE-i, and inside the loop you also say with an if that j+1 < SIZE-i should hold. So why don't you make that the loop condition and get rid of the additional if condition?
for(int j=0;j+1 < SIZE-i;j++)
Now you can just say if (numbers[j] > numbers[j+1])
 
clever
 
@LewsTherin It is easy if you write your tests first.
 
tests?
 
10:53 PM
You should at least test all permutations of [1, 2, 3].
 
@FredOverflow Ssh, don't give out the secret sauce.
 
@LewsTherin Have you ever heard of unit testing in general and JUnit in particular?
 
Nope
@RMartinhoFernandes why? lol
 
Getting any algorithm right without tests is next to impossible.
Instead of posting code and asking "Is this correct?", writing a small program that checks some interesting inputs and their results will make you a lot more productive.
 
It's far easier to exhibit incorrect behaviour for a program/algorithm than prove its correctness.
 
10:56 PM
Inputs that are interesting? Interesting =P
 
Because you will always make fencepost errors unless your name is Donald Knuth.
(< should have been <=, i should have been i+1 etc.)
@LewsTherin Interesting inputs are interesting.
The 6 different permutations of [1, 2, 3] are interesting. However, testing [1, 2, 3] and [10, 20, 30] and [11, 22, 33] is a waste of time. It is very unlikely that your algorithm works for one of those but not the other two.
 
Why should it be <= or i+1
or is it just an example?
 
@FredOverflow I prefer the term obi-wan errors.
 
@LewsTherin Those are just examples of fencepost errors that have absolutely nothing to do with your code.
 
@FredOverflow right writing code down it is pen and paper
@RMartinhoFernandes nice
 
11:00 PM
Let's say implementing Bubble sort would have been my interview question. The decision to hire you would have looked like this:
bool hire()
{
    return drew_a_diagram_before_implementing
        && implementation_looks_reasonable
        && can_correct_the_errors_when_pointed_out
        || implementation_is_flawless;
}
 
So, no hire?
 
If you don't draw a diagram first, I won't hire you, unless your implementation is flawless.
@RMartinhoFernandes I don't know if you drew a diagram, and I can't really see your reasoning at work over the Internet.
 
@FredOverflow: A diagram? I'm not sure I've drawn one.
 
Well, my implementation is flawless, so...
:)
 
11:02 PM
@MooingDuck Yes, because a diagram with a simple input will immediately point out several interesting things, for example that you only need SIZE-1 outer iterations.
 
@FredOverflow meeean :(
 
If you're good, you will also see that after the n-th iteration, the n elements at the right are already in their final position, so you don't need to touch them again.
@LewsTherin Because if you have 10 elements, there are only 9 neighbor pairs.
 
yes true
 
Anyway, here is the implementation I came up with without testing:
void bubblesort(int numbers[], int SIZE)
{
    for (int bound = SIZE; bound > 1; --bound)
    {
        for (int i = 1; i < bound; ++i)
        {
            if (numbers[i-1] > numbers[i])
            {
                int temp = numbers[i-1];
                numbers[i-1] = numbers[i];
                numbers[i] = temp;
            }
        }
    }
}
Testing showed no errors, so I'm reasonably confident that my solution is correct.
 
Going to sleep in depression :(
 
11:05 PM
@FredOverflow Prove it!
 
@FredOverflow: Gutsy. I tend to avoid --bound loops, as writing decrementing loops and then later changing i to unsigned int has hosed me too many times.
 
@RMartinhoFernandes It works for all permutations of [1, 2, 3], that's good enough for me.
Hey, that rhymes!
 
no meter, though. fail
 
@MooingDuck I'm pretty sure bound > 1 is not a problem for unsigned :)
 
@MooingDuck When I type an unsigned type my brain switches to paranoid sign detection mode.
 
11:07 PM
@cHao what
 
@FredOverflow Meter is a property of verse.
 
too deeply nested or what?
 
yeah, that. :)
 
@FredOverflow: in this case you wouldn't have a problem. I just avoid it to avoid accidental future errors by myself and others.
 
In poetry, meter (metre in British English) is the basic rhythmic structure of a verse or lines in verse. Many traditional verse forms prescribe a specific verse meter, or a certain set of meters alternating in a particular order. The study of meters and forms of versification is known as prosody. (Within linguistics, "prosody" is used in a more general sense that includes not only poetical meter but also the rhythmic aspects of prose, whether formal or informal, which vary from language to language, and sometimes between poetic traditions.) Qualitative vs. quantitative meter The meter...
 
11:08 PM
@MooingDuck Are you telling Bubble Sort needs maintenance? The occasional refill of oxygen or what :)
 
And I just learned it's metre in British. I thought only the SI unit was like that.
@FredOverflow Yes, it needs. Refactoring into insertion sort, at least.
 
damn brits always gotta misspell stuff.
 
@FredOverflow: I've seen too many people maintain it, yes. "We made it thread safe!" (Why were you calling it twice at the same time from two threads on the same data?)
 
@LewsTherin If you want to learn about devising solutions and testing them, again I recommend "Programming Pearls".
 
My work has a thread safe std::string :(
 
11:10 PM
@MooingDuck My idea of thread safe bubble sort is: { lock guard(mutex); bubble_sort(the_thing); }
 
why were you calling it at all? :P i don't see a practical case for bubble sort over, say, std::sort
 
@MooingDuck I'm sure any sorting algorithm would be pretty pissed if another thread started modifying the input sequence :)
 
Of course, it is only thread safe as long as no other function uses the_thing without acquiring mutex.
 
@cHao: I tried to write a library sort to sort evenly distributed integers to beat std::sort. Turns out std::sort is freakin fast.
 
@FredOverflow course I want to learn...no choice
 
11:11 PM
@cHao You cannot expect people to implement std::sort during a 15 minute interview.
 
Really have to sleep..good night
 
@FredOverflow Is quicksort a valid implementation?
 
you can't expect to put code that people wrote in a 15-minute interview into production either. :)
 
I can write quicksorts by heart.
 
@RMartinhoFernandes No, std::sort has pretty hard worst case guarantees that a simple quicksort cannot offer.
 
11:12 PM
Mergesort?
 
@RMartinhoFernandes Without error? I would like to see that!
 
@FredOverflow When I did competitive programming (in C) I didn't knew about qsort.
 
@RMartinhoFernandes "Quicksort first, but after log n recursive instantiations, Mergesort" is a popular implementation, yes.
 
Is that the one called introsort?
 
@RMartinhoFernandes qsort isn't necessarily quicksort. In fact, it's rather unlikely due to quicksort's O(n^2) worst case.
 
11:14 PM
@LucDanton Similar but with heapsort.
@FredOverflow Well, point is, I didn't knew about a sorting function in the standard library. So, roll my own it was.
 
@RMartinhoFernandes Oh, maybe it was quicksort combined with heapsort, I don't remember.
@RMartinhoFernandes And you can really write Quicksort from scratch without making errors? That's pretty impressive. Hire! ;)
 
Ok, I haven't done it in a while, I could be rusty.
 
@RMartinhoFernandes I used to write my own linked lists and sorting algorithms in C++ because I didn't know there were standard containers and algorithms :)
Oh wait, that was probably before 1998...
 
is it 291 ms(milisekund) fast enough for Goldbach function, for n=100 000 000 ?
 
11:20 PM
That depends on the computer.
 
Will this implementation be called to compute the codes to prevent launching of nuclear warheads in the next 200 ms?
 
Will this implementation be called to display the result to an unsuspecting user in a GUI somewhere?
 
@Srle Which BigInt library do you use?
 
@Srle Really, only you can tell if it's "fast enough".
 
11:38 PM
Jeez. Why do sound and graphics libraries have to be so ridiculously complex? I just need a simple playSound("foo.wav"); function, but I have to trudge through pages of tutorials and documentation.
 
@Maxpm On what platform? On Windows, you can play a .wav file just about that easily.
 
Linux.
 
@Maxpm That would be a whole different story. MS hasn't done sound as well as I'd like, but Linux is still much, much worse (and, I should add, I can't really help with it much either).
 
Simple things should be simple.
I've yet to see a library where changing a single pixel is as easy as it should be.
 
How do you change a pixel on a wav file?
 
11:45 PM
> Jeez. Why do sound and graphics libraries[...]
 
Can't construct a pair from a two-tuple, weird.
 
11:56 PM
Ugh, this is frustrating.
 
A technical corrigendum doesn't usually add stuff, right? Only fix things?
 

« first day (345 days earlier)      last day (4605 days later) »