5. The Dance with Trees | Haskell Data Analysis cookbook

Sign In Start Free Trial

Book Overview & Buying
Table Of Contents

Haskell Data Analysis cookbook

By : Nishant Shukla

3.7 (6)

Haskell Data Analysis cookbook

3.7 (6)

By: Nishant Shukla

Overview of this book

Step-by-step recipes filled with practical code samples and engaging examples demonstrate Haskell in practice, and then the concepts behind the code. This book shows functional developers and analysts how to leverage their existing knowledge of Haskell specifically for high-quality data analysis. A good understanding of data sets and functional programming is assumed.

Preface

Preface

What this book covers

What you need for this book

Who this book is for

Conventions

Reader feedback

Customer support

Free Chapter

1. The Hunt for Data

1. The Hunt for Data

Introduction

Harnessing data from various sources

Accumulating text data from a file path

Catching I/O code faults

Keeping and representing data from a CSV file

Examining a JSON file with the aeson package

Reading an XML file using the HXT package

Capturing table rows from an HTML page

Understanding how to perform HTTP GET requests

Learning how to perform HTTP POST requests

Traversing online directories for data

Using MongoDB queries in Haskell

Reading from a remote MongoDB server

Exploring data from a SQLite database

2. Integrity and Inspection

2. Integrity and Inspection

Introduction

Trimming excess whitespace

Ignoring punctuation and specific characters

Coping with unexpected or missing input

Validating records by matching regular expressions

Lexing and parsing an e-mail address

Deduplication of nonconflicting data items

Deduplication of conflicting data items

Implementing a frequency table using Data.List

Implementing a frequency table using Data.MultiSet

Computing the Manhattan distance

Computing the Euclidean distance

Comparing scaled data using the Pearson correlation coefficient

Comparing sparse data using cosine similarity

3. The Science of Words

3. The Science of Words

Introduction

Displaying a number in another base

Reading a number from another base

Searching for a substring using Data.ByteString

Searching a string using the Boyer-Moore-Horspool algorithm

Searching a string using the Rabin-Karp algorithm

Splitting a string on lines, words, or arbitrary tokens

Finding the longest common subsequence

Computing a phonetic code

Computing the edit distance

Computing the Jaro-Winkler distance between two strings

Finding strings within one-edit distance

Fixing spelling mistakes

4. Data Hashing

4. Data Hashing

Introduction

Hashing a primitive data type

Hashing a custom data type

Running popular cryptographic hash functions

Running a cryptographic checksum on a file

Performing fast comparisons between data types

Using a high-performance hash table

Using Google's CityHash hash functions for strings

Computing a Geohash for location coordinates

Using a bloom filter to remove unique items

Running MurmurHash, a simple but speedy hashing algorithm

Measuring image similarity with perceptual hashes

5. The Dance with Trees

5. The Dance with Trees

Introduction

Defining a binary tree data type

Defining a rose tree (multiway tree) data type

Traversing a tree depth-first

Traversing a tree breadth-first

Implementing a Foldable instance for a tree

Calculating the height of a tree

Implementing a binary search tree data structure

Verifying the order property of a binary search tree

Using a self-balancing tree

Implementing a min-heap data structure

Encoding a string using a Huffman tree

Decoding a Huffman code

6. Graph Fundamentals

6. Graph Fundamentals

Introduction

Representing a graph from a list of edges

Representing a graph from an adjacency list

Conducting a topological sort on a graph

Traversing a graph depth-first

Traversing a graph breadth-first

Visualizing a graph using Graphviz

Using Directed Acyclic Word Graphs

Working with hexagonal and square grid networks

Finding maximal cliques in a graph

Determining whether any two graphs are isomorphic

7. Statistics and Analysis

7. Statistics and Analysis

Introduction

Calculating a moving average

Calculating a moving median

Approximating a linear regression

Approximating a quadratic regression

Obtaining the covariance matrix from samples

Finding all unique pairings in a list

Using the Pearson correlation coefficient

Evaluating a Bayesian network

Creating a data structure for playing cards

Using a Markov chain to generate text

Creating n-grams from a list

Creating a neural network perceptron

8. Clustering and Classification

8. Clustering and Classification

Introduction

Implementing the k-means clustering algorithm

Implementing hierarchical clustering

Using a hierarchical clustering library

Finding the number of clusters

Clustering words by their lexemes

Classifying the parts of speech of words

Identifying key words in a corpus of text

Training a parts-of-speech tagger

Implementing a decision tree classifier

Implementing a k-Nearest Neighbors classifier

Visualizing points using Graphics.EasyPlot

9. Parallel and Concurrent Design

9. Parallel and Concurrent Design

Introduction

Using the Haskell Runtime System options

Evaluating a procedure in parallel

Controlling parallel algorithms in sequence

Forking I/O actions for concurrency

Communicating with a forked I/O action

Killing forked threads

Parallelizing pure functions using the Par monad

Mapping over a list in parallel

Accessing tuple elements in parallel

Implementing MapReduce to count word frequencies

Manipulating images in parallel using Repa

Benchmarking runtime performance in Haskell

Using the criterion package to measure performance

Benchmarking runtime performance in the terminal

10. Real-time Data

10. Real-time Data

Introduction

Streaming Twitter for real-time sentiment analysis

Reading IRC chat room messages

Responding to IRC messages

Polling a web server for latest updates

Detecting real-time file directory changes

Communicating in real time through sockets

Detecting faces and eyes through a camera stream

Streaming camera frames for template matching

11. Visualizing Data

11. Visualizing Data

Introduction

Plotting a line chart using Google's Chart API

Plotting a pie chart using Google's Chart API

Plotting bar graphs using Google's Chart API

Displaying a line graph using gnuplot

Displaying a scatter plot of two-dimensional points

Interacting with points in a three-dimensional space

Visualizing a graph network

Customizing the looks of a graph network diagram

Rendering a bar graph in JavaScript using D3.js

Rendering a scatter plot in JavaScript using D3.js

Diagramming a path from a list of vectors

12. Exporting and Presenting

12. Exporting and Presenting

Introduction

Exporting data to a CSV file

Exporting data as JSON

Using SQLite to store data

Saving data to a MongoDB database

Presenting results in an HTML web page

Creating a LaTeX table to display results

Personalizing messages using a text template

Exporting matrix values to a file

Index

Index

Calculating the height of a tree

The height of a tree is the length of the longest downward path from the root node. For example, the height of a balanced binary tree should be around log to the base 2 of the number of nodes.

Getting ready

As long as we're consistent, the height of a tree can be defined as either the number of nodes or the number of edges in the longest path. In this recipe, we will count by using the number of nodes. The longest path of this tree contains three nodes and two edges. Therefore, this tree has a height of three units.

How to do it...

Import the maximum function from Data.List and the built-in tree data structure from Data.Tree:
```
import Data.List (maximum)
import Data.Tree
```

Define a function to calculate the height of a tree:

height :: Tree a -> Int

height (Node val []) = 1
height (Node val xs) = 1 + maximum (map height xs)

Construct a tree on which we will run our algorithm:

someTree :: Tree Integer

someTree = root
  where root = 0 [n1, n4]
        n1   = 1 [n2,...

CONTINUE READING

83

Tech Concepts

36

Programming languages

73

Tech Tools

Unlimited access to the largest independent learning library in tech of over 8,000 expert-authored tech books and videos.

Innovative learning tools, including AI book assistants, code context explainers, and text-to-speech.

50+ new titles added per month and exclusive early access to books as they are being written.

Haskell Data Analysis cookbook

Search

Your notes and bookmarks