Algebraic Data Types in Swift

An algebraic data type is a type that’s the union of other data types. That is, it’s a type that may be one of several other types. Here’s how we would implement a linked list as an algebraic data type in Swift:

enum LinkedList<Element> {  
    case empty
    indirect case node(data: Element, next: LinkedList)
}

This defines an enum called LinkedList that might either be .empty or a .node that points to another LinkedList. There are three interesting things to note. The first is that we’ve created a generic data type, so the type of Element is declared by the consumer of LinkedList. The second is that the .node case uses LinkedList recursively, and must therefore be marked with indirect. The third is that since the .empty case has no parameters, the parenthesis may be omitted.

Here’s how we define instances of LinkedList:

let a: LinkedList<Int> = .empty  
let b: LinkedList<Int> = .node(data: 1, next: .node(data: 2, next: .empty))  

To work with an algebraic data type, we deconstruct it using pattern matching. Here’s how we would print a LinkedList:

enum LinkedList<Element>: CustomStringConvertible {  
    '' // cases omitted for brevity
    var description: String {
        switch self {
        case .empty:
        return "(end)"
        case let .node(data, next):
        return "(data), (next.description)"
        }
    }
}

let b: LinkedList<Int> = .node(data: 1, next: .node(data: 2, next: .empty))

print("b: (b)") // => b: 1, 2, (end)  

We’ve implemented the CustomStringConvertible protocol so that we can use string interpolation to print LinkedList instances. While it is possible in Swift to pattern match using an if case statement, the switch is preferable because the compiler will warn us if we’ve forgotten to handle a case. This safety is one big advantage that algebraic data types have over their classical counterparts. In a traditionally implemented linked list, you would have to remember to check if the next pointer was null to know if you were at the end. This problem gets worse as the number of cases increase in more complex data structures, such as full binary range trees with sentinels.

Note that since the description instance variable only has a getter, we do not need to use the more verbose syntax:

var description = {  
    get {
        // etc
    }
    set {
        // etc
    }
}

Our print function was useful, but in order to do interesting things we need to be able to modify algebraic data types. Rather than mutate the existing data structure, we’ll return a new data structure that represents the result after the requested operation. Since we’re not going to mutate the original data structure, we’ll follow the Swift 3 naming convention of using a gerund for our methods. Here’s how we would add an .inserting method to LinkedList:

enum LinkedList<Element>: CustomStringConvertible {  
    // cases and "description" omitted for brevity
    func inserting(e: Element) -> LinkedList<Element> {
        switch self {
            case .empty:
            return .node(data: e, next: .empty)
            case .node:
            return .node(data: e, next: self)
        }
    }
}

let c = b.inserting(e: 0)  
print("c: (c)") // => c: 0, 1, 2, (end)  

The key is that we’re returning a new LinkedList that represents the result after the insertion. Notice how in the .node case, we do not need to pattern match on .node(data, next) because data and next are not needed in order to construct the new .node; we can simply use self as the next: node.

Finally, let’s implement the classic “reverse a linked list” interview question using our algebraic data type:

enum LinkedList<Element>: CustomStringConvertible {  
    // cases, "description", and "insert" omitted for brevity
    func appending(_ e: Element) -> LinkedList<Element> {
        switch self {
            case .empty:
            return .node(data: e, next: .empty)
            case let .node(oldData, next):
            return .node(data: oldData, next: next.appending(e))
        }
    }

    func reversed() -> LinkedList<Element> {
        switch self {
            case .empty:
            return self
            case let .node(data, next):
            return next.reversed().appending(data)
        }
    }
}

print("reversed c: (c.reversed())") // => reversed c: 2, 1, 0, (end)  

I’ll leave it as an exercise to the reader to figure out what the running time for this algorithm is.

Here’s the Playground on GitHub

Notes on Higher Education and the New Society

higher-education-and-the-new-society-cover

I picked this little book up at a secondhand shop in Adams Morgan a couple of weeks ago. Keller was a professor at Johns Hopkins University, where he specialized in higher education. Higher Education and the New Society was published in 2008, a year after his death.

Keller thinks that many critics of higher education are exaggerating the stubbornness of his beloved institution. He backs this up by summarizing the last hundred and fifty years of American history, and pointing out how higher education has responded to the dramatic changes in society. Keller concedes that while higher education has been changing, those changes have been incremental. The major systems and structures haven’t changed since the 1910s, when the first and only revolution in American higher education happened. He concludes with three proposals for change.

My Notes
  • Higher education is not an institution that exists in isolation. Educational systems change in response to society. In order to critique the current state of higher education, one must also understand what changes in society have happened.
  • Major transformations in society:
    • Younger generations are influenced by friends and the media. Older generations are influenced by community leaders, and familial elders.
    • Changing Demographics
      • A plummeting fertility rate means that the population is aging
      • The elderly are wealthier than ever.
      • Immigration has rapidly increased, and 90% of immigrants are coming from Latin America, Asia, and Africa. Prior to 1965, 70% of immigrants were from Europe.
      • The nuclear family is crumbling. The divorce rate has doubled, 36% of children are born out of wedlock, and many 60% of children will spend part of their childhood in a single parent home.
      • “We find it easier to love others if we ourselves have been loved. We learn self-sacrifice as we learn so many other things — in small, managable steps, starting close to home.”
      • Good parenting is a better predictor of a child’s success than affluence.
      • The first six years of a child’s life, to a large extent, determines academic achievement later.
      • Two-parent families serve as a bank and venture capital fund for their children.
      • Illegitimacy and divorce are responsible for essentially all the growth in poverty since 1970.
      • Interracial relationships are increasing, which means that the current system of classifying students by race will break down as racially ambiguous students become the norm.
      • The internet might fundamentally change education, but that remains to be seen — the same was said about television in 1957.
    • Changing Economics
      • The US was relatively unscathed after WWII, and siezed the opportunity to build the mightiest economy in the world. The 1960s were a golden age. The US government was flush with money, and compassionate liberals poured money into federal aid and research universities.
      • In the 1970s, the economic boom eroded. It was a decade of deterioration and disruptive change.
        • High quality goods from Japan and Germany led to the US becoming a net importer.
        • The outbreak of global terrorism resulted in the formation of a costly department of homeland security.
        • Inflation rose to 17% at one point, before drastic measures and a recession cut it back down to 3.8%.
        • US leaders could not rein in the spending that started in the 1960s and doubled taxes instead.
        • Watergate happened, and the news media became more hostile and adversarial. Polls revealed that the public had a widespread new contempt for authority.
        • The globalization of trade caused the US to transition into a knowledge economy. American companies farmed lower-skill manufacturing out to other nations and refocused their efforts on inventing new technologies, making scientific advances, and innovating in marketing. Scientifically educated and internationally attuned people were now in high demand, causing disciplines like History to fall into decline.
      • The US has performed admirably in the new global economy. More wealth has been created since 1983 than in the previous 150 years.
        • The demand for “skill” is the root cause of income inequality.
        • Colleges were the primary producers of high level skills.
        • More students hoped to go to college and study a professional field rather than the liberal arts.
        • The new economy lifted the best professors to new heights of affluence, influence, and importance.
        • “Intellectuals rose to the status of a privileged class” – Christopher Lasch
        • The top universities now admit based on academic achievement, and downplay the importance of family, fame, and alumni connections.
    • There are four major types of universities
      • Research Universities. These prestigious universities are a copious new source of new ideas, scientific findings, and discoveries.
      • Small Liberal Arts Colleges. The most sentimentally revered segment, they train students holistically for leadership and public service.
      • State colleges, polytechnics, proprietary schools, and small private colleges. These institutions provide the country with essential middle-range workers.
      • Two-year community and private colleges that enroll 40 percent of all students in higher education. They prepare people for vocational tasks.
    • The United States has made much progress towards equal opportunity for all. This has led to sometimes ironic results.
      • The already high degree of individualism in the US has increased.
      • Those who take advantage of the new opportunities have been richly rewarded. However, those who have not embraced the new openness earn much less and experience greater difficulty.
      • The rich and successful become more arrogant and feel they are richly deserving, but the poor become more sulky, angry, violent, and self-destructive and wonder whom to blame. “Every year, it becomes more difficult to use ant external barrier as an excuse” – Michael Young
  • Contrary to popular belief, colleges have adapted
    • Admissions offices are now grander than ever, and are frequently colocated with the financial aid office, as colleges make an effort to woo students of every race, from every corner of the country.
    • There are more classes for working adults and the elderly. Harvard makes $150 million a year from adults — 10% of its budget.
    • Colleges have also made changes to accommodate the torrent of immigrants, such as English as a Second Language classes.
    • In response to the dissolving nuclear family, colleges have increased financial aid packages and increased student affairs staff to handle the growing volume of date rape, harassment, and plagiarism cases.
    • Regarding computer technology…
      • Universities have heavily invested in computer technology, and often have CIOs in their cabinet.
      • “People don’t become physicists by learning formulas… Learning involves inhabiting the streets of a community’s culture.”
      • IT has not lowered the cost of higher education. It has increased it.
    • The significant increase in cost of higher education is not unique. It is happening in other service fields like healthcare, legal services, fine dining, and theatrical performances.
      • Slow growth in productivity compared to other activities. You can’t make a symphony orchestra that much more productive.
      • Labor intensive personal attention is required. You can’t reduce the labor cost of a chef or surgeon without serious loss of quality.
      • Highly trained expert personnel are required. These people are very expensive.
      • Costly equipment is needed, like medical devices or stage props and sets.
      • Expanding demand for a scarce number of extraordinary people.
    • Colleges have adapted to rising costs by investing their endowments in hedge funds instead of historically safe stocks, and reducing their annual withdrawal from endowment.
    • Colleges became less effective as they lowered costs.
      • Princeton closed its department of Statistics, and Columbia ended its department of Geography.
      • Colleges are employing many more part time professors, and are using graduate students to teach lower-class undergraduates. In 1980 one in four professors were part time. In 2001 only one in four new professors were on a tenure track position.
      • America is using higher education to accelerate social change. This means classifying students as a member of some group that merits special treatment, instead of treating each student as a thinking individual. The aim of a liberal education should be to “liberate our students from the contingencies of their backgrounds” (Searle). However, many professors have lifted political transformation above the disinterested pursuit of the truth.
  • The critics saying that higher education needs a massive overhaul have a point.
    • The changes in higher education since the 1970s have been incremental, and were accomplished in the same century-old structures.
    • The only academic revolution to happen in the US was between 1870 and 1910. This was when colleges got academic departments and majors, deans and presidents, electives, research and graduate programs, numbered courses and a credit system, academics relevant to industry, tenure, alumni associations, and organized fund raising. It was propelled by the desire to scrap the heavy emphasis on Latin, Greek, and Christian pedagogy and connect higher education to the actual conditions of the emerging American economy. It was kicked off by the Morrill Act of 1863, that established land-grant colleges.
    • There is tension between the three aims of higher education: preparation for work, well-rounded and deeply grounded learning, research and scholarship. To quote Aristotle, “It throws no light on the problem whether the proper studies to be followed are those which are useful in life, or those which make for goodness, or those which advance the bounds of knowledge. Each sort of study receives some votes in its favor.”
    • The semester system is a holdover from America’s agricultural past.
    • Graduate programs are devoted to research, not to the craft of teaching
    • Higher education used to be for the elite 15% that completed secondary education. Today, more than 60% of high school graduates go to college. This means that there are many more less academically prepared and less motivated students in college. Colleges are designed to educate a small elite for research, not masses of people.
    • “A multi billion dollar industry has developed outside established education institutions, responding in more direct, and usually more effective ways to the needs of industry and the labor market” – Michael Gibbons
    • Universities used to train high-minded people like von Humboldt and Newman, who pursued knowledge for knowledge’s sake. Today, they’re expected to train qualified manpower and producing knowledge for society’s benefit.
    • Only fifty or sixty of the 3800 accredited colleges in the US are premier research universities. At the rest of them, teaching is most important.
  • Proposals for change
    • Replace many four year colleges with three year programs. More students are taking AP tests, so many students are entering with sophomore status. They’re also older, and need less grooming. Many students are graduating in seven semesters. At Johns Hopkins, 20% of students complete at least one semester early.
    • Abolish the semester system. Students are no longer needed to plant crops in the spring and harvest in the fall. This would allow colleges to operate for an additional three months a year. Students would be able to complete their degrees more quickly, and facilities wouldn’t be wasted lying dormant for months.
    • Reform the sports programs at Division I universities. Big time sports have nothing to do with education, and are run as businesses that drain millions of dollars of the university’s money, while enjoying tax-exempt status. The students in these sport programs are not there for the education — 40% of basketball players do not graduate — they’re there because the only way to become a highly paid professional is to go through an education institution.