程序代写 Data Structures for Collections

Data Structures for Collections
Copyright © 2018 by . All Rights Reserved.

Learning Outcomes

by the End of the Lecture, Students that Complete
the Recommended Exercises should be Able to:
Explain How Tuples and Lists are Used in Different Selector Functions
Use List Comprehensions
Practice the “Generate-Test-Transform” Design Pattern
Copyright © 2018 by . All Rights Reserved.

Reading and Suggested Exercises
Copyright © 2018 by . All Rights Reserved.
Read the following Chapter(s):
Chapter 2: “An intro to lists” “Texas ranges” “Tuples”

Data Structures for Collections
Tuples and Lists are two Common Structures (i.e., seen in many different programming languages) for combining Several Data Elements
in Haskell, Tuples are Analogous to Structs in C or Classes comprised of Public Fields in Java, but Lists have a Recursive Definition and have more in common with Linked Lists than Arrays
Copyright © 2018 by . All Rights Reserved.

Data Structures for Collections
the Number of Elements in a Tuple is Fixed and each Element can have a Different Data Type
the Number of Elements in a List is Arbitrary and can Grow or Shrink but each Element must have the Same Data Type
Copyright © 2018 by . All Rights Reserved.

Examples of Tuple Types: (Char, Integer)
(Integer, Integer, Integer, Integer)
Examples of Tuple Values: (‘a’, 97)
(0, 1, 1, 2)
Copyright © 2018 by . All Rights Reserved.
Tuples in Haskell

the Elements of 2-Tuples (i.e., Tuples with only Two Elements, known as Ordered Pairs) can be Accessed using Selector Functions
fst (‘a’, 97) = ‘a’ snd (‘a’, 97) = 97
(n.b., those are the parentheses used to indicate that the argument is a single tuple and not two separate arguments – function arguments need not be enclosed in parentheses)
Copyright © 2018 by . All Rights Reserved.
Tuples in in with Tuple-Type Parameters can
have Components Extracted by Pattern Matching the Sum of the Elements of a 2-Tuple
(for instance) would have the Type Declaration: sum :: (Integer, Integer) -> Integer
Definition without fst / snd: sum (a, b) = a + b Definition using fst / snd: sum x = (fst x) + (snd x)
Copyright © 2018 by . All Rights Reserved.

How would you Implement a Function for Computing the Sum of Two Pairs…
with Pattern Matching?
without Pattern Matching (i.e., using fst and snd)?
Copyright © 2018 by . All Rights Reserved.
Tuples in Haskell

first Create the Type Declaration:
then Create the Function Definition:
Copyright © 2018 by . All Rights Reserved.
Tuples in Haskell

first Create the Type Declaration:
sum :: (Integer, Integer) -> (Integer, Integer)
-> (Integer, Integer)
then Create the Function Definition: sum (a, b) (c, d) = (a + c, b + d)
Copyright © 2018 by . All Rights Reserved.
Tuples in Haskell

first Create the Type Declaration:
sum :: (Integer, Integer) -> (Integer, Integer)
-> (Integer, Integer)
then Create the Function Definition: sum x y = (fst x + fst y, snd x + snd y)
Copyright © 2018 by . All Rights Reserved.
Tuples in about the Sum of Two Triples? Without Pattern Matching?
Copyright © 2018 by . All Rights Reserved.
Tuples in in Haskell
the fst / snd Functions were Defined for 2-Tuples
so Additional Selector Functions are Required How can you Implement Selector Functions for
3-Tuples (also known as Triples)? (Use Pattern Matching)
Copyright © 2018 by . All Rights Reserved.

first Create the Type Declarations:
get1stOf3 :: (Int, Int, Int) -> Int
get2ndOf3 :: (Int, Int, Int) -> Int get3rdOf3 :: (Int, Int, Int) -> Int
then Create the Function Definitions:
get1stOf3 (a, b, c) = a get2ndOf3 (a, b, c) = b get3rdOf3 (a, b, c) = c
Copyright © 2018 by . All Rights Reserved.
Tuples in about 3-Tuples of Non-Integers?
(i.e., Can we make the Declarations More General?)
Copyright © 2018 by . All Rights Reserved.
Tuples in Haskell

first Create the Type Declarations:
get1stOf3 :: (x, y, z) -> x
get2ndOf3 :: (x, y, z) -> y get3rdOf3 :: (x, y, z) -> z
then Create the Function Definitions:
get1stOf3 (a, b, c) = a get2ndOf3 (a, b, c) = b get3rdOf3 (a, b, c) = c
Copyright © 2018 by . All Rights Reserved.
Tuples in it really Necessary to Use Three Variables when you are only trying to Extract a Single Element?
(i.e., Can we make the Definitions Simpler?)
Copyright © 2018 by . All Rights Reserved.
Tuples in Haskell

first Create the Type Declarations:
get1stOf3 :: (x, y, z) -> x
get2ndOf3 :: (x, y, z) -> y get3rdOf3 :: (x, y, z) -> z
then Create the Function Definitions:
get1stOf3 (a, _, _) = a get2ndOf3 (_, b, _) = b get3rdOf3 (_, _, c) = c
Copyright © 2018 by . All Rights Reserved.
Tuples in of List Types: [Integer]
Examples of Tuple Values: [1, 2, 3, 4]
[‘C’, ‘O’, ‘M’, ‘P’, ‘3’, ‘0’, ‘0’, ‘7’]
i.e., a string
Copyright © 2018 by . All Rights Reserved.
Lists in Haskell

although it is tempting to think of the List as simply a Container for a Collection of Elements, it is very Natural and Useful to consider Lists as Recursively Defined Structures
How can you implement a Linked List in Java? Copyright © 2018 by . All Rights Reserved.
Lists in Haskell

class Node {
public Integer data; public Node next;
public Node() {
this.data = null;
this.next = null;
class List {
public Node head;
public List() {
this.head = null;
Copyright © 2018 by . All Rights Reserved.
Lists in Java

public static void main(String[] args) {
List theList = new List(); for (int i = 0; i < 5; i++) { Node theNode = new Node(); theNode.data = i; theNode.next = theList.head; theList.head = theNode; Node iter = theList.head; while (iter != null) { System.out.print(" [ " + iter.data + " ] -> “); iter = iter.next;
} System.out.println(“null”);
Copyright © 2018 by . All Rights Reserved.
Lists in Java

there is Another Solution that Does Not Use a Separate Class for the Nodes of the List…
Copyright © 2018 by . All Rights Reserved.
Lists in Java

class List {
public Integer head; public List tail;
public List() {
this.head = null;
this.tail = null;
Copyright © 2018 by . All Rights Reserved.
Lists in Java

public static void main(String[] args) {
List theList = new List(); for (int i = 0; i < 5; i++) { List newList = new List(); newList.head = i; newList.tail = theList; theList = newList; List iter = theList; while (iter.head != null) { System.out.print(" [ " + iter.head + " ] -> “); iter = iter.tail;
} System.out.println(“null”);
Copyright © 2018 by . All Rights Reserved.
Lists in Java

Lists in Java
in the latter solution, a List was Either:
Two Null References (i.e., an Empty List) or
an Integer Encapsulated with Another List
this is a Recursive Definition (with a Single Base Case)
Copyright © 2018 by . All Rights Reserved.

Lists in Haskell
a List is an Element (usually denoted head) that is
Appended to a another List (usually denoted tail) head
Copyright © 2018 by . All Rights Reserved.

Lists in Haskell although Less Common (but occasionally useful),
a List can also be Defined in the Other Direction last
Copyright © 2018 by . All Rights Reserved.

head [1, 2, 3, 4] = 1
last [1, 2, 3, 4] = 4 tail [1, 2, 3, 4] = [2, 3, 4] init [1, 2, 3, 4] = [1, 2, 3]
in Haskell, Lists can be written as Comma-Separated sequences placed inside Square Brackets
Copyright © 2018 by . All Rights Reserved.
Lists in Haskell

although it is Common Practice to Write Lists using Commas, it is easy to imagine a Function for Encapsulating a Head with a Tail
in λ-Calculus, a List of Elements 𝒆𝟏, 𝒆𝟐, 𝒆𝟑, … 𝒆𝒏 could be Written 𝝀𝒇𝒙. 𝒇𝒆𝟏(𝒇𝒆𝟐 𝒇𝒆𝟑 … 𝒇𝒆𝒏𝒙 … ))
Equivalently, consider the following Expression 𝐟𝐨𝐨 𝒆𝟏 (𝐟𝐨𝐨 𝒆𝟐(𝐟𝐨𝐨 𝒆𝟑 … (𝐟𝐨𝐨 𝒆𝒏 ∅)))
Lists in © 2018 by . All Rights Reserved.

the Infix List Constructor Operator (:) Appends the Left Operand (which is an Element) to the Front of the Right Operand (which is a List)
1 : [2, 3, 4, 5] = [1, 2, 3, 4, 5]
1 : (2 : (3 : (4 : [5]))) = [1, 2, 3, 4, 5] 1 : [] = [1]
[] : [] = [[]]
Copyright © 2018 by . All Rights Reserved.
Lists in would you Implement a Function for Computing the Sum of the Elements of a List after Dividing the elements into Groups of Three…
with Pattern Matching?
without Pattern Matching (i.e., using head and tail)?
Copyright © 2018 by . All Rights Reserved.
Lists in Haskell

the Infix List Concatenation Operator (++) Joins the Operands (which are both Lists) into a Single List (i.e., Left followed by Right, In Order)
[1, 2] ++ [3, 4, 5] = [1, 2, 3, 4, 5] [] ++ [3, 4, 5] = [3, 4, 5]
[1, 2] ++ [] = [1, 2]
[] ++ [] = []
Copyright © 2018 by . All Rights Reserved.
Lists in Haskell

in Haskell, the String Data Type is Equivalent to a List of Chars (i.e., [Char])
consequently, Every List Function (e.g., head, tail) or Operation (:, ++) can also take String Arguments
Copyright © 2018 by . All Rights Reserved.
Lists in in Haskell
in fact, the Double Quotation Marks are actually
Shorthand for the Square Bracket List Notation
Both of the following Expressions to True: “HELLO” == [‘H’, ‘E’, ‘L’, ‘L’, ‘O’]
“HELLO” == ‘H’ : (‘E’ : (‘L’ : (‘L’ : (‘O’ : []))))
Copyright © 2018 by . All Rights Reserved.

List Comprehensions
in Discrete Mathematics, the Elements of Sets
are often Listed Exhaustively… e.g., h𝑒𝑎𝑟𝑡𝑠,𝑑𝑖𝑎𝑚𝑜𝑛𝑑𝑠,𝑠𝑝𝑎𝑑𝑒𝑠,𝑐𝑙𝑢𝑏𝑠
…but can Also be written using Set Builder Notation e.g., 𝑥|𝑥∈𝑆∧𝑝 𝑥 ∧𝑝 𝑥 ∧⋯𝑝 𝑥
Many Languages (including Haskell) can employ something Analogous to Set Builder Notation for Advanced List Construction
Copyright © 2018 by . All Rights Reserved.

List Comprehensions
List Comprehension is a Characteristic of Functional Programming that has become a part of Modern Scripting Languages
it allows for the Creation of very Compact and Elegant Solutions using a “Generate-Test-Transform” Design Pattern
Copyright © 2018 by . All Rights Reserved.

List Comprehensions
Assumingthats = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], theListComprehension[ 2*n | n <- s, n > 3 ] creates a List of the Double of Every Element of s that is Greater Than 3, in the Order they Appear in s
<- is Analogous to ∈, so n <- s "Generates" the Values , is Analogous to ∧, so n > 3 “Tests” the Values and 2 * n “Transforms” the Values
Copyright © 2018 by . All Rights Reserved.

List Comprehensions
the Candidates for List Comprehension can be
Extracted using Pattern Matching addPairs :: [(Int, Int)] -> [Int]
addPairs lst = [m + n | (m, n) <- lst] Each Element of the Argument List Matches the Pattern (m, n), so it is Divided into its Components and the Transformation Expression computes the Sum Copyright © 2018 by . All Rights Reserved. List Comprehensions Assuming the existence of the length function for computing the Length of a List... How would you Write a Function in Haskell that Takes a List of Lists of Integers as an Argument and Produces a List of the Heads of All of the Lists Containing an Odd Number of Elements as a Result? Copyright © 2018 by . All Rights Reserved. List Comprehensions foo :: [Integer] -> [Integer]
foo [] = []
foo (h:t) = (foo [x | x <- t, x <= h]) ++ [h] ++ (foo [x | x <- t, x > h])
What does this Function Achieve?
Copyright © 2018 by . All Rights Reserved.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts