Mutable Sequences

Mutable Sequences

"Building Blocks" of programs

-   primitive expressions

-   arithmetic expressions

-   call expressions

Managing complexity

Representing collections of Data

What are Containers good for ?

: allow us to store related values together

 ( can process the values one-by-one or in aggregate )

 ( allows us to form compound values through data abstraction )

: give rise to a number of ways of storing values

 ( lists store in order, associated with an index )

 ( dictionaries have no order but associate values with any sort of key )

 ( trees allow for a hierarchical representation of data )

The many uses of Trees

Trees show up in

-   efficiently searching data ( Autocomplete )

-   artificial intelligence ( game Trees / the minimax algorithm )

-   machine learning ( decision Tree )

-   computational biology ( Suffix Trees, Phylogenetic Trees )

-   programming languages ( Syntax and Expression Tree )

-   operating systems ( File structure )

Mutability

Using Compound Values

-   data abstraction allows us to think about compound values as units, or objects

-   but compound values have state that change over time; they are mutable

-   so far, we treated all our values as immutable; we only create new objects, never changing them

Making New Objects

: only make new list

: new variable pointing to same list

Mutation Operations

List Mutation

append ( el ) : adds el to the end of the list

insert ( i, el ) : inserts el at index i

extend ( seq ) : adds elements in seq one by one to the end of the list

remove ( el ) : removes the first occurence of el from the list

pop ( i ) : removes and returns the element at index i

Immutable Values

-   Strings

-   Tuples

Mutating within functions

Identity Versus Equality

Identity : <expr0> is <expr1>

   evaluates to True if both <expr0> and <expr1> evaluate to the same object

Equality : <expr0> == <expr1>

   evaluates to True of both <expr0> and <expr1> evaluates to equal values

Identical values are always equal values

Identity vs. Equality in Environment Diagrams

- review : for assignment statements, evaluate the right side, then assign to the left

- copying : when creating a copy, copy exactly what's "in the box"

At each step, determine :

1. what will the box-and-pointer diagrams look like ?

2. which lists are equal

3. which lists are identical

Mutability can be dangerous

-   In general, don't use mutability unless you have to

: usually if you expect the function to have the side-effect of mutating the list

: when you have to, make sure the effects are limited to as few frames as possible

-   sometimes mutability makes your code simpler, but it also makes it more complex

 

Summary

-   In order to give power to certain types of compound data, we need a way for its value to change over time

: list and dictionaries have methods for changing their value over time

: some values are immutable and their value cannot be changed

-   It is important to keep track of when variables are identical versus just equal, since mutating one variable will mutate all other identical variables