Programmig Newbie....where to start?

[Malcolm McLean]

Is your change of wording deliberate? I was talking about expressing an
algorithm, not implementing it. For example, here is one way to express
an algorithm whose value is the Fibonacci sequence (all of it!) in
Haskell:

fib = 1 : 1 : map (uncurry (+)) (zip fib (tail fib))

Now, this works on my machine, so it's implementable using just the
instructions my CPU executes, but it can't, I contend, be expressed in C
without totally distorting the meaning of the word "express".

Depends what you mean. I don't know Haskell so I've got to guess, but it looks like
the algorithm does a look up as a special case for 1 and 2, then does addition
to calculate the rest, by using the "tail recursion" optimisation.

In C you can express it a repeated addition, or recursively, but you can't easily
express that the definition is both recursive and implementable by repeated addition.
You can use big numbers in C, but not tidily. I don't know if Haskell allows you
to express that for many uses of the function, little integers will suffice.
We can easily enough get an array of Fibonnaci numbers in C. but it's much more
difficult to get both the array of numbers and the Nth number without using
N slots of memory.

So I'd say, yes, Haskell can express ideas that C can't. It can give a single interface to
an algorithm whilst C can only give one interface (unless you write highly complex
and non-idiomatic C).

 

[Ben Bacarisse]

What he's asking for is a description of a program or function, which "you can't
write in C".

Not as far as I can see. In this question he has kept my wording, so he
is asking about expressing an algorithm, rather than writing a program.

That's literally impossible, of course, because of the theorem of
Turing equivalence

Smiley noted, but someone might not know what you mean by that.

But maybe someone can come up with something that
can't reasonably be written in C.

I did in my reply, using both meanings: a program that can be written
in C, and an algorithm that can't be expressed in C.

 

[Ben Bacarisse]

Hmm.

I can imagine something like this:

struct lazy_evaluated_list {
/* blah blah */
};

along with a bunch of auxiliary declarations that let you build and
manipulate these lists.

You clearly can't translate that Haskell code to C code with anything
like the same simplicity, but I think you can write C code that
corresponds to it fairly closely.

I can't say for sure, but I think not. Many years ago I tried to do
just that, but I decided that it did not really express the same thing,
simply because of all the mess. However, I can't say for sure. Any
takers? I'd love to see a natty version of this in C.

(At worst, you can just write a Haskell implemention in C; perhaps
that's cheating.)

Yes, I consider that cheating. The point is about expressing an
algorithm, rather than writing a program.

 

[Ben Bacarisse]

Depends what you mean.

Yes, most definitely. It's a judgement call. Well, more than one in
fact, because first you have to say when the word "express" has lost
it's meaning. Is there now so much machinery and detail that the ideas
are lost? Secondly, you have to make a judgement about how much is
algorithm and how much is implementation.

This code works by applying a function to a list of pairs, and that list
is made from two others, which happen to the fib sequence and the fib
offset by one. These seem to me to be the keys parts that are
"algorithm". The fact that Haskell needs a technical dance (uncurry
(+)) two express the pair-adding function is not, to my mind, intrinsic
to the algorithm. If it were, the task would be much harder.

I don't know Haskell so I've got to guess, but it looks like
the algorithm does a look up as a special case for 1 and 2, then does addition
to calculate the rest, by using the "tail recursion" optimisation.

At some level, yes, but this defines a list not a function. To use it
one would access an element (fib!!10000) or do other list-like things to
it. For that reason, a C expression of the method should be as
list or array-like as possible. I'm not sure how close you can get with
that aspect.

In C you can express it a repeated addition, or recursively, but you can't easily
express that the definition is both recursive and implementable by
repeated addition.
You can use big numbers in C, but not tidily. I don't know if Haskell allows you
to express that for many uses of the function, little integers will
suffice.

It uses big-nums. I don't think that's key to expressing the algorithm.
It may be awkward to re-write numerical code to use an arbitrary
precision arithmetic library, but the impact on the expression of the
algorithm is not massive.

We can easily enough get an array of Fibonnaci numbers in C. but it's much more
difficult to get both the array of numbers and the Nth number without using
N slots of memory.

Haskell is not know for its parsimony in respect of memory!

<snip>

 

[Malcolm McLean]

At some level, yes, but this defines a list not a function. To use it
one would access an element (fib!!10000) or do other list-like things to
it. For that reason, a C expression of the method should be as
list or array-like as possible. I'm not sure how close you can get with
that aspect.

OK, psi is the sum of the reciprocals of the Fibonnaci numbers.

So presumably there's a concise Haskell expression that will
evaluate to psi by using the list. How many digits can you get?

 

[Ben Bacarisse]

OK, psi is the sum of the reciprocals of the Fibonnaci numbers.

(usually phi)

So presumably there's a concise Haskell expression that will
evaluate to psi by using the list. How many digits can you get?

How many do you want? You need a high-precision float package to do any
of this as Haskell only has rationals and plain old double-precision
floats built-in, but there is a "computable real" package where you
decide on the precision only when you come to print.

The list of approximations can be done with the same trick of offset
lists (zipWidth avoids the uncurry call):

phi_approximations = zipWith ldiv (tail fib) fib
where ldiv :: Integer -> Integer -> CReal
ldiv a b = (fromInteger a)/(fromInteger b)

To get sensible printing, you want to print about twice the number of
digits as there are digits in the Fibonacci numbers being divided, so
you could have a helper function (!! is the list index operator):

phi_show n = showCReal (2*ndigits) (phi_approximations !! n)
where ndigits = length $ show $ fib !! n

About 0.6 seconds for nearly 42,000 digits. That's from the 100,000th
approximation, i.e. the ratio of Fibonacci numbers 100,000 and 100,001.
I have no idea if that is fast or not -- I've not tried any other
method.

As for your actual question about there being a concise expression for
this, I am not good at Haskell golf. I am sure there is a neater
expression, but I won't try to find it.

 

[Kaz Kylheku]

Is your change of wording deliberate? I was talking about expressing an
algorithm, not implementing it. For example, here is one way to express
an algorithm whose value is the Fibonacci sequence (all of it!) in
Haskell:

fib = 1 : 1 : map (uncurry (+)) (zip fib (tail fib))

Now, this works on my machine, so it's implementable using just the
instructions my CPU executes, but it can't, I contend, be expressed in C
without totally distorting the meaning of the word "express".

Off the top of my head, this is imitable in TXR Lisp as follows, with an
explicit destructive manipulation to close the self-reference:

@(do
(defun fib ()
(let ((fib (list 1 1)))
(rplacd (cdr fib) [mapcar* + fib (rest fib)])
fib))

(prinl [(fib) 0..15]))

The basic concept is the same: overlap the fib sequence with itself,
shifted by one position, and map through + to lazily continue, using
(1 1) to get it started.

Run:

$ txr fib.txr
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597)

And so with that, it's obvious it can can be translated to intrinsic C code
roughly like this:

val fib(void)
{
val fib = cons(one, cons(one, nil));
rplacd(cdr(fib), lazy_mapcarv(func_n2(plus),
cons(fib, cons(rest(fib), nil))));
return fib;
}

I'm not going bother testing this because I just know it works.

Do you know the song, "Write in C"? Sing it with me!

 

[David Brown]

(usually phi)


How many do you want? You need a high-precision float package to do any
of this as Haskell only has rationals and plain old double-precision
floats built-in, but there is a "computable real" package where you
decide on the precision only when you come to print.

The list of approximations can be done with the same trick of offset
lists (zipWidth avoids the uncurry call):

phi_approximations = zipWith ldiv (tail fib) fib
where ldiv :: Integer -> Integer -> CReal
ldiv a b = (fromInteger a)/(fromInteger b)

To get sensible printing, you want to print about twice the number of
digits as there are digits in the Fibonacci numbers being divided, so
you could have a helper function (!! is the list index operator):

phi_show n = showCReal (2*ndigits) (phi_approximations !! n)
where ndigits = length $ show $ fib !! n

About 0.6 seconds for nearly 42,000 digits. That's from the 100,000th
approximation, i.e. the ratio of Fibonacci numbers 100,000 and 100,001.
I have no idea if that is fast or not -- I've not tried any other
method.

As for your actual question about there being a concise expression for
this, I am not good at Haskell golf. I am sure there is a neater
expression, but I won't try to find it.

It should also be perfectly possible to use a list of integer digits for
decimals and for unlimited range integers, rather than standard floating
point numbers. Make your integers as finite lists, and your ratio as an
infinite list, using lazy evaluation. It's a /long/ time since I did
this sort of thing, but at university I wrote a program in a functional
programming language (not Haskell, but quite similar) to calculate the
digits of pi in this way (from the Taylor series for atan(1/4)). The
only limit on the output was due to memory on the computer, and the
patience of the operator - the algorithm was not particularly efficient,
but the program was elegant.

 

[Malcolm McLean]

(usually phi)

phi is the ratio of the N+1/Nth Fibonnaci number, as N approaches
infinity. But it also has a simple closed form expression.

psi is the sum of the reciprocals, i.e.
1/1 + 1/1 + 1/2 + 1/3 + 1/5 + 1/8 ...

You need to calculate psi by summing, there is no closed form
solution.

 

[BartC]

phi is the ratio of the N+1/Nth Fibonnaci number, as N approaches
infinity. But it also has a simple closed form expression.

psi is the sum of the reciprocals, i.e.
1/1 + 1/1 + 1/2 + 1/3 + 1/5 + 1/8 ...

You need to calculate psi by summing, there is no closed form
solution.

Unless you need an exact value, this series seems to converge very quickly
(to about 3.359886). You don't really need to sum all the terms.

 

[Ben Bacarisse]

Is your change of wording deliberate? I was talking about expressing an
algorithm, not implementing it. For example, here is one way to express
an algorithm whose value is the Fibonacci sequence (all of it!) in
Haskell:

fib = 1 : 1 : map (uncurry (+)) (zip fib (tail fib))

Now, this works on my machine, so it's implementable using just the
instructions my CPU executes, but it can't, I contend, be expressed in C
without totally distorting the meaning of the word "express".

Off the top of my head, this is imitable in TXR Lisp as follows, with an
explicit destructive manipulation to close the self-reference:

@(do
(defun fib ()
(let ((fib (list 1 1)))
(rplacd (cdr fib) [mapcar* + fib (rest fib)])
fib))

(prinl [(fib) 0..15]))

The basic concept is the same: overlap the fib sequence with itself,
shifted by one position, and map through + to lazily continue, using
(1 1) to get it started.

Run:

$ txr fib.txr
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597)

And so with that, it's obvious it can can be translated to intrinsic C code
roughly like this:

val fib(void)
{
val fib = cons(one, cons(one, nil));
rplacd(cdr(fib), lazy_mapcarv(func_n2(plus),
cons(fib, cons(rest(fib), nil))));
return fib;
}

I'm not going bother testing this because I just know it works.

Sure. I know that too. The question is the algorithm. Here you
overwrite a cell to make a circular structure. Is that the same
algorithm? I think it is debatable, but, to be honest, maybe it is not
worth debating. We should maybe just agrees that some things are
clearer and simpler to express in some languages. Questions of
judgement and degree often generate more heat the light on Usenet.

Do you know the song, "Write in C"? Sing it with me!

No, is it in the key of D?

 

[Ben Bacarisse]

It should also be perfectly possible to use a list of integer digits for
decimals and for unlimited range integers, rather than standard floating
point numbers.

I don't use standard floating point numbers. I am sure the CReal
package does something like you suggest. I'm just avoiding duplicating
that work.

<snip>

 

[Kaz Kylheku]

Can you give an example (or several) of an algorithm that cannot be
implemented in C or in assembly language?

Is your change of wording deliberate? I was talking about expressing an
algorithm, not implementing it. For example, here is one way to express
an algorithm whose value is the Fibonacci sequence (all of it!) in
Haskell:

fib = 1 : 1 : map (uncurry (+)) (zip fib (tail fib))

Now, this works on my machine, so it's implementable using just the
instructions my CPU executes, but it can't, I contend, be expressed in C
without totally distorting the meaning of the word "express".

Off the top of my head, this is imitable in TXR Lisp as follows, with an
explicit destructive manipulation to close the self-reference:

@(do
(defun fib ()
(let ((fib (list 1 1)))
(rplacd (cdr fib) [mapcar* + fib (rest fib)])
fib))

(prinl [(fib) 0..15]))

The basic concept is the same: overlap the fib sequence with itself,
shifted by one position, and map through + to lazily continue, using
(1 1) to get it started.

Run:

$ txr fib.txr
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597)

And so with that, it's obvious it can can be translated to intrinsic C code
roughly like this:

val fib(void)
{
val fib = cons(one, cons(one, nil));
rplacd(cdr(fib), lazy_mapcarv(func_n2(plus),
cons(fib, cons(rest(fib), nil))));
return fib;
}

I'm not going bother testing this because I just know it works.

Sure. I know that too. The question is the algorithm. Here you
overwrite a cell to make a circular structure. Is that the same
algorithm?

It's not exactly the same, but it's not very distant either.

In the interpreted version where I use "let", I could make an operator which
provides syntactic sugar for closing the self-reference which hides the
destructive manipulation.

The main concept is there: it's a small capsule of code which sets up a lazy
structure corresponding to the Fibonacci series, produced by a function which
maps + over its own results, shifted by one place.

On the other hand, note that though I needed destructive assignment, I didn't
need to "zip" the sequences together to form pairs, and then "uncurry" the +
function to apply it to the pairs.

I think it is debatable, but, to be honest, maybe it is not
worth debating. We should maybe just agrees that some things are
clearer and simpler to express in some languages.

The Haskell may be direct (something rare for Haskell), but it's obfuscated as
heck.

This is way clearer and simpler to understand:

(defun fib ()
(let ((fib (list 1 1)))
(rplacd (cdr fib) [mapcar* + fib (rest fib)])
fib))

After you read this, you can exhale: "Ah, so that's the straightforward
nuts and bolts of what the Haskell code is essentially doing".

 

[Ben Bacarisse]

phi is the ratio of the N+1/Nth Fibonnaci number, as N approaches
infinity. But it also has a simple closed form expression.

psi is the sum of the reciprocals, i.e.
1/1 + 1/1 + 1/2 + 1/3 + 1/5 + 1/8 ...

You need to calculate psi by summing, there is no closed form
solution.

Oh, I misread the question entirely, which is a shame because it is,
perhaps, a little simpler (though slower to compute). One way (surely
far less than optimal) is to write:

phi_approximation :: [CReal]
phi_approximation = scanl1 (+) (map (1/) (map fromInteger fib))

and then just print this list. Alternatively, print an element and the
next to see how many digits you've got right (yes, that's a rubbish
method, but I don't want to spend much time on this). To get 1000
digits takes about 0.6s.

 

[Ben Bacarisse]

Unless you need an exact value, this series seems to converge very
quickly (to about 3.359886). You don't really need to sum all the
terms.

That usually means better than linear. The convergence appears to be
liner, but appearances can be deceiving.

 

[Ben Bacarisse]

[...] The
only limit on the output was due to memory on the computer, and the
patience of the operator - the algorithm was not particularly efficient,
but the program was elegant.

I think I know what you mean -- an algorithm the just puts out decimal
digits one by one (usually getting slower and slower!) for as long as
you care to wait. If so, my last reply missed the point. Sorry.

Yes, such a think is probably possible, (and they are very neat
algorithms) but I went a different way round.

 

[Ben Bacarisse]

It's not exactly the same, but it's not very distant either.

In the interpreted version where I use "let", I could make an operator which
provides syntactic sugar for closing the self-reference which hides the
destructive manipulation.

The main concept is there: it's a small capsule of code which sets up a lazy
structure corresponding to the Fibonacci series, produced by a function which
maps + over its own results, shifted by one place.

On the other hand, note that though I needed destructive assignment, I didn't
need to "zip" the sequences together to form pairs, and then "uncurry" the +
function to apply it to the pairs.

Yup, but if you consider zipping up two lists as part of the algorithm,
then that's a part that's not been "expressed". (I think the uncurry
(+) is of no significance -- in fact I should probably have used zipWith:

fib = 1 : 1 : zipWith (+) fib (tail fib)

).

The Haskell may be direct (something rare for Haskell), but it's obfuscated as
heck.

This is way clearer and simpler to understand:

(defun fib ()
(let ((fib (list 1 1)))
(rplacd (cdr fib) [mapcar* + fib (rest fib)])
fib))

I bet there will a few raised eyebrows at that remark!

After you read this, you can exhale: "Ah, so that's the straightforward
nuts and bolts of what the Haskell code is essentially doing".

I find the Haskell very clear, but then I've been using it, and it's
direct predecessors, for as long as I've been programming. Mind you,
I've been using Lisp for about as long, so I am also very much at home
with your version too. To me, they express slightly different things,
but I may have set too fine a resolution on my algorithm detector.

 

[BartC]

This is way clearer and simpler to understand:

(defun fib ()
(let ((fib (list 1 1)))
(rplacd (cdr fib) [mapcar* + fib (rest fib)])
fib))

I bet there will a few raised eyebrows at that remark!

Possibly people wondering at the meaning of the square brackets.

Maybe the first could be part of the identifier, but the second matching one
by itself seems a bit of a coincidence.

 

[Kaz Kylheku]

Yup, but if you consider zipping up two lists as part of the algorithm,
then that's a part that's not been "expressed".

That part of the algorithm seems to reflect the coder's belief
(right or wrong) that Haskell has no nice way to map over multiple lists.

Zipping two lists into a list of corresponding pairs is just is
(mapcar list list1 list2). If what we really want is to add
corresponding list entries, we want (mapcar + list1 list2).
Lisps usually have an N argument mapcar that will march through
N lists in parallel and feed N arguments to the function.

If all you have is "zip" and a map function that takes only unary
functions and one list, then you need some hack workaround, like
using a version of + that takes a list pair. You zip the lists up
into pairs just so you can then map the pairs into this +.

(I think the uncurry
(+) is of no significance -- in fact I should probably have used zipWith:

fib = 1 : 1 : zipWith (+) fib (tail fib)

Aha, so there is your (mapcar + list1 list2); it is just called zipWith.

I see that this doesn't take three lists! For that there is ...
wait for it ... zipWith3.

Camel case and numeric suffixes for number of arguments, *barf*.

Why don't they just call this language Hassle?

It makes things like "func_n1(plus)" in my C version look good!

 

[Kaz Kylheku]

This is way clearer and simpler to understand:

(defun fib ()
(let ((fib (list 1 1)))
(rplacd (cdr fib) [mapcar* + fib (rest fib)])
fib))

I bet there will a few raised eyebrows at that remark!

Possibly people wondering at the meaning of the square brackets.

Those are the best use ever of square brackets in a Lisp dialect.

Square brackets denote Lisp-1 style evaluation. Forms directly enclosed in
square brackets which are symbols are evaluated in a folded function/variable
namespace. This is beneficial for programming with higher-order functions,
and with objects that behave like functions.

Instead of (call var arg) or (mapcar (fun foo) list) you just write
[var arg] or [mapcar foo list].

Because sequences are functions (which map index positions to elements), square
brackets provide indexing: [array 42]. Also, hash lookup: [hash foo].

Basically, I have found a very clean, pragmatic way to combine Lisp-1 and
Lisp-2, obtaining all the advantages of both.