Haskell Cons Operator (:)

Question

I am really new to Haskell (Actually I saw "Real World Haskell" from O'Reilly and thought "hmm, I think I'll learn functional programming" yesterday) and I am wondering: I can use the construct operator to add an item to the beginning of a list:

1 : [2,3]
[1,2,3]

I tried making an example data type I found in the book and then playing with it:

--in a file
data BillingInfo = CreditCard Int String String
| CashOnDelivery
| Invoice Int
deriving (Show)

--in ghci
 $ let order_list = [Invoice 2345]
 $ order_list
[Invoice 2345]
 $ let order_list = CashOnDelivery : order_list
 $ order_list
[CashOnDelivery, CashOnDelivery, CashOnDelivery, CashOnDelivery, CashOnDelivery, CashOnDelivery, CashOnDelivery, CashOnDelivery, CashOnDelivery, CashOnDelivery, CashOnDelivery, CashOnDelivery, CashOnDelivery, CashOnDelivery, ...-

etc... it just repeats forever, is this because it uses lazy evaluation?

-- EDIT --

okay, so it is being pounded into my head that let order_list = CashOnDelivery:order_list doesn't add CashOnDelivery to the original order_list and then set the result to order_list, but instead is recursive and creates an infinite list, forever adding CashOnDelivery to the beginning of itself. Of course now I remember that Haskell is a functional language and I can't change the value of the original order_list, so what should I do for a simple "tack this on to the end (or beginning, whatever) of this list?" Make a function which takes a list and BillingInfo as arguments, and then return a list?

-- EDIT 2 --

well, based on all the answers I'm getting and the lack of being able to pass an object by reference and mutate variables (such as I'm used to)... I think that I have just asked this question prematurely and that I really need to delve further into the functional paradigm before I can expect to really understand the answers to my questions... I guess what i was looking for was how to write a function or something, taking a list and an item, and returning a list under the same name so the function could be called more than once, without changing the name every time (as if it was actually a program which would add actual orders to an order list, and the user wouldn't have to think of a new name for the list each time, but rather append an item to the same list).

Answer 1

The cdr of the cons you've just created points back to itself: the definition of order_list used in the second let is the definition being created. Use a different variable name to sidestep the recursion issue altogether, and the code will also be less confusing.

EDIT: After reading Joel's answer, it seems I'm speaking with a Lisp here. Lazy evaluation or no, in any case you've created a recursive definition...

Answer 2

Haskell uses lazy evaluation... nothing gets evaluated until it's needed, which is why order_list is stored as a cons containing CashOnDelivery and another, unevaluated cell referencing order_list again.

Answer 3

I think you mean "is this because it uses lazy evaluation"? The answer is yes:

let ol = CashOnDelivery : ol

This tells us that ol contains the element CashOnDelivery, and then the result of the expression ol. This expression is not evaluated until necessary (hence: laziness). So, when ol is printed, CashOnDelivery will be printed first. Only then will the next element of the list be determined, hence leading to infinite behavior.

Answer 4

Yes, you are trying to print an infinite list that you can create with lazy evaluation. For example

let a = 1 : a

creates infinite list of ones, and you can take as many of them as you want with the take function, or when trying to print it. Note that you use the same identifier on the left and right hand sides of the equation, and it works: order_list is CashOnDelivery:order_list, now substituting: order_list = CashOnDelivery:(CashOnDelivery:order_list) = Cash... etc.

If you wanted to create [Cash..., Invoice] list, don't reuse names like that.

Answer 5

X:L means "Create a list starting with X followed by the items in the list defined by L."

You are then defining order_list to be CashOnDelivery followed by the items in the list defined order_list. This definition is recursive, which is why the list evaluation keeps returning CashOnDelivery. Your list actually contains an infinate number of CashOnDelivery values followed by a single Invoice value.

Answer 6

Answer to question edit:

so what should I do for a simple "tack this on to the end (or beginning, whatever) of this list?" Make a function which takes a list and BillingInfo as arguments, and then return a list?

Ah, but there already is a "function" for prepending a element to list: it is the cons (:) constructor :-)

So your existing code will work just fine, as long as you don't use the same name for two different variables, because the second name binding will shadow (hide) the first.

ghci> let first_order_list = [Invoice 2345]
ghci> first_order_list
[Invoice 2345]
ghci> let second_order_list = CashOnDelivery : first_order_list
ghci> second_order_list
[CashOnDelivery, Invoice 2345]

---

Regarding the second edit:

Since your asking how you would do something like this in an actual program, I would say this:

If your repeatedly adding things to a list you don't want to invent new names for that list every time. But the keyword here is "repeatedly", in imperative programming you would use a loop here (and modifying some variable in the loop).

Because this is functional programming, you can't use loops, but you can use recursion. Here's how I would write a program that allows a user to enter orders and collects a list:

main = do
  orderList <- collectBillingInfos
  putStrLn ("You entered these billing infos:\n" ++ show orderList)

collectBillingInfos :: IO [BillingInfo]
collectBillingInfos = loop []
  where
    loop xs = do
      putStrLn "Enter billing info (or quit)"
      line <- getLine
      if line /= "quit"
        then loop (parseBillingInfo line : xs)
        else return xs

parseBillingInfo :: String -> BillingInfo
parseBillingInfo _ = CashOnDelivery -- Don't want to write a parser here

To recap; the loop function is calling itself recursively, each time with a new element added to the list. Until the user enters "quit", then it stops calling itself and returns the final list.

---

Original answer relating to lazy evaluation:

As others have said, this is a recursive definition, making order_list an infinite list containing just CashOnDelivery values. While lazy evaluation isn't the cause of it, it does make it useful.

Because of lazy evaluation you can use order_list like this:

ghci> take 3 order_list
[CashOnDelivery, CashOnDelivery, CashOnDelivery]

If you didn't have lazy evaluation, the call to take would crash, because it would first try to evaluate order_list (which is infinite).

Now, for order_list this isn't really useful, but there are many other places where being able to program with infinite (or just very large) data structures is very convenient.

Answer 7

You do this:

$ let order_list = [Invoice 2345]
$ let order_list = CashOnDelivery : order_list

The important thing to note here is that you are not just adding a CashOnDelivery item to your first order_list. You are defining a new variable order_list that has nothing to do with the first one. This is a recursive definition, the order_list on the right side refers to the order_list you are defining on the left, not the one defined in the previous line. Because of this recursion you get an infinite list.

I suspect you really wanted to do something like this:

$ let order_list = [Invoice 2345]
$ order_list
[Invoice 2345]
$ let order_list2 = CashOnDelivery : order_list
$ order_list2
[CashOnDelivery, Invoice 2345]

Answer 8

I think the important issue here is not laziness but scope. The expression let x = ... introduces a new definition of x which will replace any previous definition. If x appears on the right-hand side, then the definition will be recursive. It seems you expected the use of order_list on the right-hand side of

let order_list = CashOnDelivery : order_list

to refer to the first definition of order_list (i.e., [Invoice 2345]). But the let expression introduced a new scope. Instead, you have defined an infinite list of CashOnDelivery elements.

Answer 9

order_list in this line:

let order_list = [Invoice 2345]

is a different variable from order_list in this line

let order_list = CashOnDelivery : order_list

The second line does not change the value of order_list. It introduces a new variable with the same name but a different value.

order_list on the right hand side of the second line is the same order_list as on the left hand side of the second line; it is unrelated to the order_list in the first line. You get an infinite list full of CashOnDelivery --- there are no Invoices in this second list.

Answer 10

As a recovering ML programmer, I get caught by this one all the time. It's one of the few annoyances in Haskell that you cannot easily rebind a name in let or where clauses. If you want to use let or where, you have to invent new names. At the top-level read-eval-print loop, if you want to bind one name at a time, you have no other choice. But if you are willing to nest constructs, you can abuse the do notation with the identity monad:

import Control.Monad.Identity

let order_list = runIdentity $ do
       order_list <- return [Invoice 2345]
       order_list <- return $ CashOnDelivery : order_list
       return order_list

Yes, this code is despicable---and not worth it for this example---but if I have a long list of rebindings I might resort to it so I don't have to invent 5 or 6 meaningless variations on the same name.

Answer 11

In ML, val is not recursive. You must specify val rec for recursive values.

val fin = fn _ => 0
val fin = fn x => fin x + 1
(* the second `fin` is calling the first `fin` *)

val rec inf = fn x => inf x + 1
(* ML must be explicitly told to allow recursion... *)
fun inf' x = inf' x + 1
(* though `fun` is a shortcut to define possibly recursive functions *)

In Haskell, all top-level, let, and where bindings are recursive -- there is no non-recursive binding.

let inf = \_ -> 0
let inf = \x -> inf x + 1
-- the second `inf` completely shadows the first `inf`

The exception: in do, <- binding is not recursive. However, if you use {-# LANGUAGE RecursiveDo #-} and import Control.Monad.Fix, you get mdo, in which a <- binding is recursive.

foo :: Maybe [Int]
foo = do
    x <- return [1]
    x <- return (0 : x)  -- rhs `x` refers to previous `x`
    return x
-- foo == Just [0, 1]

bar :: Maybe [Int]
bar = mdo
    y <- return (0 : y)  -- rhs `x` refers to lhs `x`
    return y
-- bar == Just [0, 0, 0, ...]