Re: Q: Efficiency of Array Implementation

[Jan Laitenberger]

Dear Mr. Mechveliani,
 

 I thought efficient arrays are impossible in functional language.

I'm not sharing this thought...   

Here is a quote from the Haskell Library Report:

\begin{quote}
  ``Haskell provides indexable arrays, which may be thought of as functions
whose domains are isomorphic to contiguous subsets of the integers.
Functions restricted in this way can be implemented efficiently;
in particular, a programmer may reasonably expect rapid access to the
components.''
\end{quote}
   
 So we have to organise the data so that to avoid the access by index
  - as possible. 

Sure. If possible - ok.


Regards,

Jan

 ___
'---|--
|  __,   _  _  EMail: [EMAIL PROTECTED]
| /  |  / |/ | WWWeb: http://www.uni-passau.de/~laitenbe/
|/\_/|_/  |  |_/
   /| Laitenberger 
--(-|--
   \|

Re: Q: Efficiency of Array Implementation

[S.D.Mechveliani]

Concerning 'rapid access' you found in docs - it is hard to believe
this access is as fast as in C array - i mean changing X[i] in array
X. Because when this change is done fast, it is a side effect, breaks
functionality.
I always thought that this is the main cost the functional world pays
for the nice functional principles - to think of how to avoid indice
in the critical parts of the algorithm.
Well, i may mistake ...

Re: Q: Efficiency of Array Implementation

[fis]

 Date: Fri, 19 Feb 1999 09:41:58 +0100 (MET)
 From: Lennart Augustsson [EMAIL PROTECTED]
 CC: [EMAIL PROTECTED], [EMAIL PROTECTED],
 [EMAIL PROTECTED]


  Concerning 'rapid access' you found in docs - it is hard to believe
  this access is as fast as in C array - i mean changing X[i] in array
  X. Because when this change is done fast, it is a side effect, breaks
  functionality.
 Extracting values from an array can be as fast as in C.  The tricky
 part is contructing the array.  The Haskell Array module provides
 one way of constructing monolithic arrays, i.e., arrays that are built
 once and never again modified.
 But there are other ways, e.g., using ST monad which allows incremental
 construction of the array.

-- Lennart


This reminds me of a question I could not solve on my own yet (due to
lack of an operational profiler for the most part): Is it possible that
ghc knows how to transform Array data structures into destructive
arrays in some settings?

I had an algorithm with a terrible time complexity and wrote an
implementation using purely functional Arrays. Since the runtime was
still to bad, I tried ST together with MutableArrays instead, but the
runtime got worse.

I don't have the time to figure out the details right now, but if you
plan to stay interested in them for a longer period, tell me and I will
give you more information when I work on the problem again. (It's still
possible that it's a bug in my code, however.)


 -Matthias





-- 
Max-Planck-Institut für Informatik  |  DFKI
[EMAIL PROTECTED]   |  [EMAIL PROTECTED]
http://www.mpi-sb.mpg.de/~fis   |