Java – I need to know how Haskell represents data and can write a good Haskell program?

I'm learning Haskell from a Java background When I program java, I think I know very well how objects are arranged in memory and the consequences For example, I know exactly Java Lang.string and Java util. How linkedlists work, so I know how I should use them I'm a little lost with Haskell For example, (:) how does it work? Should I care? Specify somewhere?

Solution

The short answer is No When programming in Haskell, you should treat data structures as purely mathematical objects without worrying about their performance in memory The reason for this is that without side effects, there is really no data except the function that creates it and the function that can be used to extract the simpler part of its construction

To view information about the data constructor, such as (:) or any other term, use the: type (or simply: t for short) command in ghci:

:Prelude> :type (:)
(:) :: a -> [a] -> [a]

This tells you that the (:) constructor (pronounced "cons") takes values of any type and lists of the same type, and returns lists of the same type You can also use the: Info command to get more information This shows how the data definition:

Prelude> :info (:)
data [] a = ... | a : [a]   -- Defined in GHC.Types
infixr 5 :

This tells you that (:) is a constructor that adds elements to an existing list

I also strongly recommend that hoogle not only find things by name, but also do the opposite search; There you know the signature of the feature you are looking for and want to find someone who has written it for you Hoogle is good because it gives descriptions and example usage

Inductive data shape

As I said above, it is not important to know the representation of data in memory, but you should understand the shape of the processed data to avoid performance degradation All data in Haskell is inductively defined, which means that it has a tree shape, which expands backward recursively You can tell the shape of the data by viewing its definition; Once you know how to read it, its performance features are really not hidden:

data MyList a = Nil | Cons a (MyList a)

As can be seen from the definition, the only way to get a new mylist is by the constructor If you use this constructor many times, you will finally get such a rough shape:

(Cons a5 (Cons a4 (Cons a3 (Cons a2 (Cons a1 Nil)))))

This is just a tree without branches. That's the definition of the list! The only way to get A1 is to pop up each Conss in turn; Therefore, the last element accessed is O (n), and the access header is a constant time Once you can do this reasoning on the data structure according to your own definition, you can complete it