Array functions?
Hello, I hope these don't turn out to be RTFM questions, but I can't find them in my FM :-) 1) Is there a function to get the ith element from an array? 2) Is there a function to get the "index" of an entry in an array? I've implemented these two functions below: 1) find 0 (x:xs) = x find n (x:xs) = find (n-1) xs 2) index i (x:xs) = if i == x then 0 else 1 + index a xs This was a fun exercise, but I can't shack off the feeling that I just re-invented the wheel. I need these because I want to be able to swap any two elements from an array. This is my swap function: -- swap i j array => swaps the ith and jth elements of 'array'. -- swap i j arr = a_head ++ [item_j] ++ a_midd ++ [item_i] ++ a_tail where a_head = [a | a <- arr, index a arr < i] item_i = find i arr a_midd = [a | a <- arr,(index a arr > i) && (index a arr < j)] item_j = find j arr a_tail = [a | a <- arr, index a arr > j] I'm sure this was a poor way to accomplish this, but it was a learning experience. If anyone would like to show me a more elegant solution, I would be happy to see it. Cheers, Daniel. Haskell newbie.
On Wednesday 04 May 2005 01:26, Daniel Carrera wrote:
Hello,
I hope these don't turn out to be RTFM questions, but I can't find them in my FM :-)
Take a look at this one: http://www.haskell.org/onlinelibrary/standard-prelude.html
1) Is there a function to get the ith element from an array?
From your own implementations I gather you mean 'list', not 'array'. In the above document search for 'index'. You find: -- List index (subscript) operator, 0-origin (!!) :: [a] -> Int -> a xs !! n | n < 0 = error "Prelude.!!: negative index" [] !! _ = error "Prelude.!!: index too large" (x:_) !! 0 = x (_:xs) !! n = xs !! (n-1)
2) Is there a function to get the "index" of an entry in an array?
This one is not so obvious. It is not in the Prelude but in teh H98 standard library, see http://www.haskell.org/onlinelibrary/list.html. You'll find elemIndex :: Eq a => a -> [a] -> Maybe Int elemIndices :: Eq a => a -> [a] -> [Int] find :: (a -> Bool) -> [a] -> Maybe a findIndex :: (a -> Bool) -> [a] -> Maybe Int findIndices :: (a -> Bool) -> [a] -> [Int] [...] 17.1 Indexing lists elemIndex val list returns the index of the first occurrence, if any, of val in list as Just index. Nothing is returned if not (val `elem` list). elemIndices val list returns an in-order list of indices, giving the occurrences of val in list. find returns the first element of a list that satisfies a predicate, or Nothing, if there is no such element. findIndex returns the corresponding index. findIndices returns a list of all such indices. Now, if you happen to also want to know these functions for real arrays, not lists, I suppose you take a look at the standard library module Array. Cheers, Ben
Hi Ben,
Take a look at this one:
Thanks. What's the "Prelude" ?
1) Is there a function to get the ith element from an array?
From your own implementations I gather you mean 'list', not 'array'.
What's the difference?
Now, if you happen to also want to know these functions for real arrays, not lists, I suppose you take a look at the standard library module Array.
Thanks for all the info! Cheers, Daniel.
Date: Tue, 03 May 2005 19:56:00 -0400 From: Daniel Carrera
Hi Ben,
Take a look at this one:
Thanks.
What's the "Prelude" ?
It's the repository of haskell code (functions, types, type classes) that is available without having to import any modules. Basically, built-in types, type classes, and functions. You can also think of it as a module that comes pre-loaded.
1) Is there a function to get the ith element from an array?
From your own implementations I gather you mean 'list', not 'array'.
What's the difference?
_Big_ difference. An array is a collection of items that provides O(1) (constant time) access to any component via indexing, and (in imperative languages) also provides constant-time changing (mutation) of any such component. A list (more specifically, a singly-linked list) is a collection of items that consists of the front element (the "head" of the list) and the rest of the list, which is another list (note that the empty list is also a list). The effect of this is that to get at an arbitrary element of a list takes time proportional to the length of the list (it's O(n), where n is the length of the list). So you don't want to use lists the same way you would use arrays -- they aren't "drop in replacements" for arrays. Doing so would result in horrendously inefficient code. You need to learn a new style of programming to work efficiently with lists, typically involving using recursion on the head/tail structure of the list. This mailing list isn't the right place to go into this in detail, but the books I mentioned before (How to Design Programs and Structure and Interpretation of Computer Programs) discuss this at great length. This is a lot of what makes functional programming hard for many people to learn; you aren't just learning a new syntax, you're learning a whole new way to think. That's also what makes it fun ;-) Mike
The first thing that I think I should mention is that lists are not
arrays. You should have a look at Data.Array
(http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Array.html)
and the other libraries in that bunch if you really want arrays (where
random access is O(1) rather than O(n))
Now, your "find" function is implemented as a library function, it is
called (!!) so xs !! n is the nth element of a list xs.
What I think you intend by index is implemented in Data.List as
elemIndex, which returns a Maybe Int, that is the value (Just n) if
the first occurrence of the desired element is at position n, and the
value (Nothing) otherwise.
Finding and then swapping two elements of a Haskell list is not a
terribly efficient thing to do.
If I had to do it directly, I'd probably write something like:
import List
swap i j xs | i == j = xs
swap i j xs | otherwise = initial ++ (xs !! b) : middle ++ (xs !! a) : end
where [a,b] = sort [i,j]
initial = take a xs
middle = take (b-a-1) (drop (a+1) xs)
end = drop (b+1) xs
which takes time and space on the order of b.
The need to do lots of swaps is probably an indication that a list is
not the data structure you're looking for though. What are you
actually trying to accomplish? There are a number of other data
structures readily available.
Have a look at the hierarchical libraries at
http://www.haskell.org/ghc/docs/latest/html/libraries/index.html
in particular at Data.Map, Data.Set, and Data.Array.*
hope this is useful :)
- Cale
On 5/3/05, Daniel Carrera
Hello,
I hope these don't turn out to be RTFM questions, but I can't find them in my FM :-)
1) Is there a function to get the ith element from an array? 2) Is there a function to get the "index" of an entry in an array?
I've implemented these two functions below:
1) find 0 (x:xs) = x find n (x:xs) = find (n-1) xs
2) index i (x:xs) = if i == x then 0 else 1 + index a xs
This was a fun exercise, but I can't shack off the feeling that I just re-invented the wheel.
I need these because I want to be able to swap any two elements from an array. This is my swap function:
-- swap i j array => swaps the ith and jth elements of 'array'. -- swap i j arr = a_head ++ [item_j] ++ a_midd ++ [item_i] ++ a_tail where a_head = [a | a <- arr, index a arr < i] item_i = find i arr a_midd = [a | a <- arr,(index a arr > i) && (index a arr < j)] item_j = find j arr a_tail = [a | a <- arr, index a arr > j]
I'm sure this was a poor way to accomplish this, but it was a learning experience. If anyone would like to show me a more elegant solution, I would be happy to see it.
Cheers, Daniel. Haskell newbie. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (4)
-
Benjamin Franksen -
Cale Gibbard -
Daniel Carrera -
Michael Vanier