Fredrik Eriksson <fe79}--at--{yahoo}--dot--{com> wrote:
> 'fold' (should probably be 'foldl1') is just a library function, not a  
> language primitive. The corresponding C++ library function is  
> 'std::accumulate'.

>    std::accumulate( my_list.begin(), my_list.end(), 0 );

  Which got me thinking: Does foldl1 in haskell work for data containers
other than lists? What if you want to apply it to only a sub-range inside
the data container rather than to the entire container? (Can you do it
without copying the sub-range to a separate container?)

-- 
                                                          - Warp

Post a reply to this message

On 23-Sep-08 0:45, Darren New wrote:
> andrel wrote:
>> OK, so there is where we part. I don't want to think about hardware or 
>> compiler issues when I am solving a problem. 
> 
> Me neither. But someone has to. If you're using a language with reserved 
> words, you're going to have to avoid them.
> 
>> Just as when I am doing math and I feel that I should need to 
>> introduce a new syntax. Standard and new syntax will form my new 
>> framework. Whatever someone else at any one time though were his 
>> fundamental concepts is immaterial to me.
> 
> Yep. Then you should be using FORTH or LISP or Tcl or something like 
> that, right? What language *do* you prefer? 

Ahumm, I mostly use Matlab ATM. That does not mean that I like its 
syntax, it is just my swiss army knife. For things that should be 
maintained we use our MWEB system (Knuth's WEB system modified for 
Matlab). That gives a slighly more expressive system. If we want to we 
can use greek variables with subscripts.
I did like FORTH, precisely for this reason.  Did I ever bore you with 
my multitasking FORTH on the C64? You can't use it for things that have 
to be readable for others. Apparently Andy understands reversed polish, 
but you can't count on that for the average modern student.
I liked Prolog and lambda calculus and functional languages. And 
probably not as a surprise, I like Dijkstra's guarded commands, mostly 
because I don't have a compiler for that*. Must check if there is one 
perhaps.

*) Just kidding of course, it is because it is closer to predicate 
calculus that any other imperative language.

> There aren't very many that let you introduce new syntax to the language.

Afraid so. Lots of stupid graphical interfaces but the use of Lexx and 
Yacc seems to be yet another art lost in the mists of time :(
Just as that you have a number of symbolic formula manupilating programs 
but non that I could find that let you apply predicate transformers on 
complicated boolean expressions interactively.
I think I am somewhat out of touch with 'modern' computer science.

> In any case, you're still going to have to explain the new syntax, which 
> means you're going to have to use a language comprehensible to your 
> listeners. You can't just make up a new language from scratch and expect 
> to be able to communicate with someone else, even if that other person's 
> brain is flexible enough to learn it if taught it.

Sure.

>> Let me reiterate, I don't even care if Haskell allows it or not. The 
>> discussion was if Haskell should visually make the distinction or not. 
>> To which my answer is no, because what is and what isn't a reserved 
>> word is too arbitrary. i.e. some are legitimate reserved (most of your 
>> examples are from that stock), some are reserved but a case could be 
>> made to relieve them of that status and some are not reserved, but 
>> might be. So fuzziness all over, hence: do not treat them visually 
>> different.
> 
> OK. I'd say I'd want them treated differently if they actually are 
> reserved. I.e., if I have a variable called "case", I'd want to see the 
> statement starting
>    case case of
> to have two different color words, for example.
> 
> I take it you don't like syntax coloring in your editor?
> 
Of course I do. I just want to be able to add a few things myself. My 
point is still the other way around ;)

Post a reply to this message

Warp wrote:

>   Which got me thinking: Does foldl1 in haskell work for data containers
> other than lists?

No. The function specified in the language standard works only for lists.

However, there *is* an alternate version in one of the libraries that 
does work for any suitable container. (Confusingly, it has the same 
name, even though it's a different function.) Almost all container 
libraries supply their own home-grown fold function, which may or may 
not have the same name and/or type signature.

This is something of a known problem. A container like lists can hold 
*any* type of data, but the Set container can only hold "ordered" data. 
We have yet to reach a concensus about how to encode this into the type 
system. (Dependent types look like the future, but that's an 
experimental new feature that isn't part of any official standard, etc.)

> What if you want to apply it to only a sub-range inside
> the data container rather than to the entire container? (Can you do it
> without copying the sub-range to a separate container?)

Notionally, no.

Physically? Ask the optimiser.

(Remember, your "container" might not actually *exist* in its entirity 
until you try to "do" something with it...)

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

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> > What if you want to apply it to only a sub-range inside
> > the data container rather than to the entire container? (Can you do it
> > without copying the sub-range to a separate container?)

> Notionally, no.

> Physically? Ask the optimiser.

  One thing which bothers me with haskell is the amount of features which
rely solely on the compiler being able to optimize them. For example a
simple thing like "go through this subrange inside this list and calculate
the sum of the elements", which you usually do in-place, becomes something
which at the language level requires copying (needlessly) the subrange just
so that you can traverse it, and hoping that the compiler will be able to
figure out what is it that you are really doing and optimizing the copying
away.

  In other words, you would have to know the internal workings and
capabilities of the specific compiler you are using in order to know
if you can do it or if you have to do it by other more difficult means
(if copying the range of elements would be way too heavy and memory
consuming to be feasible).

  I don't know... This kind of defeats the whole purpose of a high-level
language where you are supposed to not to have to worry about internal
implementation details of the compiler.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   I don't know... This kind of defeats the whole purpose of a high-level
> language where you are supposed to not to have to worry about internal
> implementation details of the compiler.

I think you could do it the same way you do it in C, if you need to: 
iterate over the list and add up only the elements you're interested in.

fold goes from yadda.begin() to yadda.end(). If you don't want to do 
that, use a different function. Or write it more iteratively, so to 
speak. Think about your C++ implementation of fold - you would have to 
copy the list there too if you wanted to use that on a subset.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Warp wrote:

>> Notionally, no.
> 
>> Physically? Ask the optimiser.
> 
>   One thing which bothers me with haskell is the amount of features which
> rely solely on the compiler being able to optimize them.

You're used to C++, where what you tell the computer to do is *exactly* 
what the computer does. (Or very close to it.)

The C++ way means that if you're clever, you can write very performant 
code. The Haskell way means that if the compiler suddenly gets smarter, 
your existing code speeds up. (Although the fact that it's speeding up 
implies that it was slower than necessary before.)

> For example a
> simple thing like "go through this subrange inside this list and calculate
> the sum of the elements", which you usually do in-place, becomes something
> which at the language level requires copying (needlessly) the subrange just
> so that you can traverse it, and hoping that the compiler will be able to
> figure out what is it that you are really doing and optimizing the copying
> away.

In this specific case, I'm particularly confident that the compiler can 
work it out. (But - as you point out - that's because I have some idea 
about how this is working internally.)

>   I don't know... This kind of defeats the whole purpose of a high-level
> language where you are supposed to not to have to worry about internal
> implementation details of the compiler.

To an extent, yes.

I think of it as being somewhat like SQL. If you write some random chunk 
of SQL, you can know what the result will be. But how will this result 
be computed? Well, *that* would depend on exactly which database product 
from which vendor with which configuration settings, what indexes have 
been built, what the size of the tables is, how the optimiser has been 
configured...

Now, if it's your job to make sure certain critical queries run fast, 
you will know the particular database you're using and what to do to the 
query to speed it up. You'll look at query plans to see what the 
database is doing, and what might be worth changing. (GHC allows you to 
do something conceptually similar.)

Does having to rephrase an SQL query to make it faster "defeat the 
purpose of SQL"? Not so much. It's unfortunate that it's necessary, but 
it doesn't stop SQL from being a hugely useful thing.

If you want to write performant code in C++, you had better go learn 
about call-by-name vs call-by-reference and how virtual methods are 
implemented and a whole bunch of stuff if you expect your code to be 
performant. C++ doesn't pretend otherwise. In Haskell, you need to have 
some idea how the abstractions you're playing with are implemented too. 
Typically you don't need a really in-depth technical understanding, but 
you do need to have some clue how the machine is doing this stuff.

I guess if you're writing something where efficiency is the absolute 
maximum priority, Haskell perhaps isn't the best possible choice. But 
for the kind of code *I* write, the program is so complicated 
algorithmically that getting it to *work properly* is the top priority. 
(Ever heard the phrase "implement first, optimise second"?) So maybe 
it's just that you and I write different code. My code tends not to be 
performance-critical.

Post a reply to this message

Actually, I have a question...

The C++ tutorial I'm reading has a section on how to inline functions. 
Now *clearly* the compiler cannot inline something that it can't *find*. 
So all that stuff about putting code into header files if you want it 
inlined across compilation units is a necessary part of the way a C++ 
compiler works. But does C++ ever inline functions within *the same* 
compilation unit automatically? Or does it literally refuse to inline 
every function that doesn't say "inline" on it?

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> fold goes from yadda.begin() to yadda.end(). If you don't want to do 
> that, use a different function. Or write it more iteratively, so to 
> speak. Think about your C++ implementation of fold - you would have to 
> copy the list there too if you wanted to use that on a subset.

  Or I could simply make an overloaded version of the fold function which
takes an iterator range.

-- 
                                                          - Warp

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> The C++ tutorial I'm reading has a section on how to inline functions. 
> Now *clearly* the compiler cannot inline something that it can't *find*. 
> So all that stuff about putting code into header files if you want it 
> inlined across compilation units is a necessary part of the way a C++ 
> compiler works. But does C++ ever inline functions within *the same* 
> compilation unit automatically? Or does it literally refuse to inline 
> every function that doesn't say "inline" on it?

  Whether the compiler will inline a function (from which it has the
implementation at that point) is unspecified and completely up to the
compiler. The 'inline' keyword doesn't really matter in this. The
compiler may well inline a function which does not have the 'inline'
keyword, and it may well not inline a function which has it. In a way,
the 'inline' keyword is a no-op, at least with respect to actual inlining.

  It's not a no-op keyword overall, because it controls how the linker
behaves with that function. If the linker encounters the same 'inline'
function in more than one object file, it will use only one of them and
make all the code which calls that function to use that one.

  If you put a function implementation in a header file, you must make
it 'inline' to avoid linker errors (if the header file is used in more
than one compilation unit). If you don't make it 'inline', you are
effectively instantiating the same function in more than one compilation
unit, and the linker considers this to be an error (name collision of
two different functions).

  (Btw, template functions are implicitly 'inline', so the keyword doesn't
have to be used with them.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   Whether the compiler will inline a function (from which it has the
> implementation at that point) is unspecified and completely up to the
> compiler. The 'inline' keyword doesn't really matter in this.

Right. So adding an inline function to a header file means that the 
compiler *could* inline it across compilation units (which would 
otherwise be impossible), but ultimately it's up to the compiler to 
decide what it will or won't inline?

I can certainly see why the standard doesn't mandate anything either 
way. Do you happen to know the "typical" behaviour of any well-known C++ 
compilers? (Presumably it varies depending on the optimisation level you 
select...)

>   (Btw, template functions are implicitly 'inline', so the keyword doesn't
> have to be used with them.)

That makes sense.

Post a reply to this message