The Inflector transforms words from singular to plural, class names to table names, modularized class names to ones without, and class names to foreign keys. The default inflections for pluralization, singularization, and uncountable words are kept in inflections.rb.
Methods
- camelize
- classify
- constantize
- dasherize
- demodulize
- foreign_key
- humanize
- inflections
- ordinalize
- pluralize
- singularize
- tableize
- titleize
- underscore
Classes and Modules
Class Inflector::InflectionsPublic Instance methods
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 112 112: def camelize(lower_case_and_underscored_word, first_letter_in_uppercase = true) 113: if first_letter_in_uppercase 114: lower_case_and_underscored_word.to_s.gsub(/\/(.?)/) { "::" + $1.upcase }.gsub(/(^|_)(.)/) { $2.upcase } 115: else 116: lower_case_and_underscored_word.first + camelize(lower_case_and_underscored_word)[1..-1] 117: end 118: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 148 148: def classify(table_name) 149: camelize(singularize(table_name)) 150: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 156 156: def constantize(camel_cased_word) 157: raise NameError, "#{camel_cased_word.inspect} is not a valid constant name!" unless 158: /^(::)?([A-Z]\w*)(::[A-Z]\w*)*$/ =~ camel_cased_word 159: 160: camel_cased_word = "::#{camel_cased_word}" unless $1 161: Object.module_eval(camel_cased_word, __FILE__, __LINE__) 162: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 132 132: def dasherize(underscored_word) 133: underscored_word.gsub(/_/, '-') 134: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 140 140: def demodulize(class_name_in_module) 141: class_name_in_module.to_s.gsub(/^.*::/, '') 142: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 152 152: def foreign_key(class_name, separate_class_name_and_id_with_underscore = true) 153: underscore(demodulize(class_name)) + (separate_class_name_and_id_with_underscore ? "_id" : "id") 154: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 136 136: def humanize(lower_case_and_underscored_word) 137: lower_case_and_underscored_word.to_s.gsub(/_id$/, "").gsub(/_/, " ").capitalize 138: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 82 82: def inflections 83: if block_given? 84: yield Inflections.instance 85: else 86: Inflections.instance 87: end 88: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 164 164: def ordinalize(number) 165: if (11..13).include?(number.to_i % 100) 166: "#{number}th" 167: else 168: case number.to_i % 10 169: when 1: "#{number}st" 170: when 2: "#{number}nd" 171: when 3: "#{number}rd" 172: else "#{number}th" 173: end 174: end 175: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 90 90: def pluralize(word) 91: result = word.to_s.dup 92: 93: if inflections.uncountables.include?(result.downcase) 94: result 95: else 96: inflections.plurals.each { |(rule, replacement)| break if result.gsub!(rule, replacement) } 97: result 98: end 99: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 101 101: def singularize(word) 102: result = word.to_s.dup 103: 104: if inflections.uncountables.include?(result.downcase) 105: result 106: else 107: inflections.singulars.each { |(rule, replacement)| break if result.gsub!(rule, replacement) } 108: result 109: end 110: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 144 144: def tableize(class_name) 145: pluralize(underscore(class_name)) 146: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 120 120: def titleize(word) 121: humanize(underscore(word)).gsub(/\b([a-z])/) { $1.capitalize } 122: end
[ show source ]
# File vendor/rails/activesupport/lib/active_support/inflector.rb, line 124 124: def underscore(camel_cased_word) 125: camel_cased_word.to_s.gsub(/::/, '/'). 126: gsub(/([A-Z]+)([A-Z][a-z])/,'\1_\2'). 127: gsub(/([a-z\d])([A-Z])/,'\1_\2'). 128: tr("-", "_"). 129: downcase 130: end


Home
Microchannel
An Act cell moving in a microchannel.
About the Model
For details about the model, we refer to the paper. Alternatively, you can check out
the following online, interactive explorables to learn more about
Cellular Potts Models
in general or the
Act-CPM,
specifically (Wortel and Textor, 2020).
Suggestions
Try the following:
- Set λact or maxact to 0. You should see that the cell
cannot break symmetry and form stable protrusions to migrate.
- Set λact back to 500 and maxact to a very high value,
e.g. 1000. Click "reseed cell". You should see that the cell again has a hard time
breaking symmetry, this time because the activity is high everywhere (and thus,
there is no polarity gradient).
- Refresh the page to go back to the default settings, and watch the cell for a while.
Click "reseed cell" a couple of times. You should see that sometimes the cell manages
to break symmetry and move persistently, while other times it takes longer because
multiple protrusions form and compete.
- Strengthen the protrusive force ΔHact by
increasing λact. You should see that the cell moves faster.
- Decrease λact to 100. You should see that the protrusion
becomes smaller, the cell moves more slowly and stops/turns often. The protrusion also
frequently "shifts" up and down even if it stays on the same side of the cell.
- At this low λact setting, now increase maxact to 100.
You should see that the activity gradient reaches farther into the cell, stabilizing the
protrusion and allowing persistent motion.
References


| Name | Type | Default value | Summary |
|---|---|---|---|
| Required | |||
| --gatkjar | File | NA | The path to the GenomeAnalysisTK.jar file |
| --referencefile | File | NA | The reference file for the bam files |
| Optional | |||
| --alignunmappedmates | Boolean | NA | Whether to align unmapped mates to alternate alleles (default true) |
| --altAlleleAlignments | List[File] | NA | Alternate allele alignments |
| --altalleleflanklength | Integer | NA | Length of flanking sequence to use for alt allele mapping |
| --altmaskfiles | List[File] | NA | The genome mask file(s) for the alternate alleles |
| --bamfilesaredisjoint | Boolean | NA | Reduces memory footprint if each input BAM file contains separate samples/libraries/read groups |
| --baminputs | List[String] | NA | One or more bam files or a bam file list (with extension .list) |
| --batchsystem | String | NA | Batch system to be used when submitting scripts from within this script (bsub/qsub) |
| --classpath | String | NA | The java classpath |
| --configfile | File | NA | Configuration property file |
| --copynumbermaskfile | File | NA | Genome mask file for regions of potentially polymorphic copy number |
| --debug | String | NA | Enable verbose output for debugging |
| --depthmaximuminsertsizeradius | Double | NA | Maximum insert size radius for read depth analysis |
| --depthminimummappingquality | Integer | NA | Minimum mapping quality for read depth analysis |
| --disablegatktraversal | Boolean | NA | Disable GATK normal walker traversal |
| --discoveryInterval | String | NA | Interval(s) for SV discovery (or file of intervals) |
| --discoveryMaximumSize | Integer | NA | Maximum event size for SV discovery |
| --discoveryMinimumSize | Integer | NA | Minimum event size for SV discovery |
| --discoveryWindowPadding | Integer | NA | Window padding for SV discovery |
| --discoveryWindowSize | Integer | NA | Window size for SV discovery |
| --duplicateoverlapthreshold | Double | NA | Overlap threshold for duplicate site filtering (default 0.5) |
| --duplicatescorethreshold | Double | NA | Concordance LOD score threshold (minimum per-sample LOD score at which events are considered non-redundant, default zero) |
| --excludereadgroup | List[String] | NA | Read group(s) to exclude or .list files of read groups |
| --exomedepthmatrixfile | String | NA | Input data matrix for exome genotyping (experimental) |
| --exomemode | String | NA | True to enable exome genotyping mode (experimental) (default is false) |
| --gendermapfile | List[File] | NA | File(s) containing the declared gender for each sample |
| --genomemaskfiles | List[File] | NA | The genome mask file(s) for the reference file |
| --inputfileindexcache | String | NA | Location where the input BAM files' indices are cached |
| --jobLogDirectory | File | NA | Directory for queue output files |
| --lsfdefaultmemlimit | Integer | NA | Override default LSF MEMLIMIT setting (in GB) |
| --lsfresource | String | NA | Resource request rusage string to supply to LSF |
| --metaDataLocation | List[String] | NA | Path to meta-data directory |
| --minimuminsertsizemapfile | File | NA | File containing a manual overrides of minimum insert size used to select read pairs |
| --nonvariantscorethreshold | Double | NA | Score threshold for non-variant site filtering (phred scale, default 13.0) |
| --out | File | NA | The output vcf file. |
| --paralleljobs | Integer | NA | Number of parallel jobs to run |
| --parallelrecords | Integer | NA | Number of records to process in each parallel job |
| --parameter | List[String] | NA | Override individual parameters from the configuration property file |
| --partitionlist | List[String] | NA | Specific partitions to rerun |
| --ploidymapfile | File | NA | Map file defining the gender-specific ploidy of each region of the reference sequence |
| --rundirectory | File | NA | Directory for auxilliary output files |
| --samplelist | List[String] | NA | Sample(s) to process or .list files of samples |
| --suppressvcfcommandlines | Boolean | NA | Flag indicating whether to suppress the command line header in the output VCF file |
| --varianttype | String | NA | Variant discovery |
| --vcfcachingdistance | Integer | NA | Caching distance for VCF records to preserve sort order (default 10K) |
Whether to align unmapped mates to alternate alleles (default true).
Alternate allele alignments.
Length of flanking sequence to use for alt allele mapping.
The genome mask file(s) for the alternate alleles.
Reduces memory footprint if each input BAM file contains separate samples/libraries/read groups.
One or more bam files or a bam file list (with extension .list).
Batch system to be used when submitting scripts from within this script (bsub/qsub).
The java classpath.
Configuration property file.
Genome mask file for regions of potentially polymorphic copy number.
Enable verbose output for debugging.
Maximum insert size radius for read depth analysis.
Minimum mapping quality for read depth analysis.
Disable GATK normal walker traversal.
Interval(s) for SV discovery (or file of intervals).
Maximum event size for SV discovery.
Minimum event size for SV discovery.
Window padding for SV discovery.
Window size for SV discovery.
Overlap threshold for duplicate site filtering (default 0.5).
Concordance LOD score threshold (minimum per-sample LOD score at which events are considered non-redundant, default zero).
Read group(s) to exclude or .list files of read groups.
Input data matrix for exome genotyping (experimental).
True to enable exome genotyping mode (experimental) (default is false).
The path to the GenomeAnalysisTK.jar file.
File(s) containing the declared gender for each sample.
The genome mask file(s) for the reference file.
Location where the input BAM files' indices are cached.
Directory for queue output files.
Override default LSF MEMLIMIT setting (in GB).
Resource request rusage string to supply to LSF.
Path to meta-data directory.
File containing a manual overrides of minimum insert size used to select read pairs.
Score threshold for non-variant site filtering (phred scale, default 13.0).
The output vcf file..
Number of parallel jobs to run.
Number of records to process in each parallel job.
Override individual parameters from the configuration property file.
Specific partitions to rerun.
Map file defining the gender-specific ploidy of each region of the reference sequence.
The reference file for the bam files.
Directory for auxilliary output files.
Sample(s) to process or .list files of samples.
Flag indicating whether to suppress the command line header in the output VCF file.
Variant discovery.
Caching distance for VCF records to preserve sort order (default 10K).
See also Documentation index | GenomeSTRiP Site | GenomeSTRiP Support
GenomeSTRiP version 1.04-r1441 built at 2014/07/14 14:26:06.


In this data-centric world, it has become increasingly important to have the ability to view how data changes in real time. This ability is important in the context of dashboards; these are the canvases on which you can tell the story of the data, so the ability to show real-time, streaming data on these dashboards can be important to your business. With Power BI's real-time streaming capabilities, you can stream data and update dashboards as soon as the data is logged.
To continue with the module scenario, you are helping Tailwind Traders understand how well their manufacturing floor is operating. The assembly line has machines that are broadcasting a telemetry event each time that they perform their functions. You are collecting those event messages and want to display them with a Power BI visual. Dashboards allow you to use streaming datasets for this purpose.
Streaming data can come from various sources, including from social media, factory sensors, service-usage metrics, and other sources that contain a constant stream of data points.
For instance, in the case with Tailwind Traders, sensors on the machines constantly send a stream of telemetry data to the IoT hub, where they will be housed in their native, messy format. From the IoT hub, you can use a stream insight job to aggregate the data, meaning that it will clean the data and quiet the noisy messages. Then, you can retrieve the data into Power BI as a streaming dataset, where you can consume the information and build the pertinent visuals.
Data that comes from a streaming dataset is not stored in a Power BI data model; instead, it is stored in a temporary cache. So, you cannot model the data with this type of dataset. The only way to visualize the data from a streaming data source is to create a tile directly on a dashboard and use a custom streaming data source. These tiles are optimized for displaying the data quickly and, because no database exists to pull the data from, these types of tiles have low latency and are best suited for data that doesn't need other transformations, such as temperature or humidity.
To visualize streaming data, you need to create a new tile directly on an existing or new dashboard.
To complete this task, go to and open a dashboard and then select Add Tile. The following window will appear, where you can select Custom Streaming Datasets under Real-Time Data.
Select Next, which will redirect you to the following window where you can choose an existing streaming dataset, or get new streaming datasets, as shown in the following image.
After you have selected the new dataset, select Next, enter the details for your streaming dataset, and then add a new streaming dataset tile. Streaming dataset tiles can be in the form of line charts, stacked bar charts, cards, and gauges and are formatted similarly to any other kind of tile.
For more information, see Real-time streaming in Power BI.


--- ---
| Download | Password | Format |
| {{ site.domain }}-client.p12 | {{ site.domain }} |
PKCS #12 |
| {{ site.domain }}-client.pem | {{ site.domain }} |
PEM |
client.p12
into Keychain Access.
client.p12
into the Your Certificates
section of the Certificate Manager.
client.pem
using the following command:yubico-piv-tool -a verify-pin -s 9a -a import-key -a import-cert -i {{ site.domain }}-client.pem


LOGO
Partnership Agreement Maker
Welcome Username,
Logout
Home
Routing Packages
Routing Templates
My Reviews
Footer
Create New Routing Package
4. Add Distribution Options
3. Add Files
2. Add Reviewers
1. Add Package Details
Routing Package Title
Which Group will have access to this Package ?
Comments
B
I
U
A
Next >
Save & Exit
Save as Draft
4. Add Distribution Options
3. Add Files
2. Add Reviewers
1.  Aenean euismod bibendum laoreet.
+ Add Reviewer
Insert Routing Template
Save as Template
Comments
Save as Draft
4. Add Distribution Options
3. Add Files
2. Add Reviewers
1. Add Package Details
Next >
Save & Exit
< Prev
Browse
+ Add More Files
Drag and drop your file here
or
Description
Browse
Drag and drop your file here
or
Description
Browse
Drag and drop your file here
or
Description
Save as Draft
4. Add Distribution Options
3. Add Files
2. Add Reviewers
1. Add Package Details
Next >
Save & Exit
< Prev
Reviewer
Firstname Lastname
Research Technical Engineer & Applicant
<EMAIL_ADDRESS>000.000.0000
Distributed when
Comments to the Reviewer
Distribution List (in order of Review)
Add Person for Distribution
Files to Distribute
File
Distribute File
Description
Filename.pdf
Lorem ipsum dolor si amet file description text
Filename.pdf
Lorem ipsum dolor si amet file description text
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Aenean euismod bibendum laoreet. Proin gravida dolor sit amet lacus accumsan et viverra justo commodo.
Agreement Marked Active
Edit
X Remove
Save as Draft
Review and Submit Routing Package
Lorem Package Name
Group
Lorem group name
Comments
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Aenean euismod bibendum laoreet. Proin gravida dolor sit amet lacus accumsan et viverra justo commodo. Proin sodales pulvinar tempor. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Nam fermentum, nulla luctus pharetra vulputate, felis tellus mollis orci, sed rhoncus sapien nunc eget.
Title
Package Details
Edit
Reviewers
Edit
Files
Edit
File
Description
Filename.pdf
Lorem ipsum dolor si amet file description text
Filename.pdf
Lorem ipsum dolor si amet file description text
Distribtion Options
Edit
Reviewer
Firstname Lastname
Research Technical Engineer & Applicant
<EMAIL_ADDRESS>000.000.0000
Distributed when
Comments to the Reviewer
Distribution List (in order of Review)
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Aenean euismod bibendum laoreet. Proin gravida dolor sit amet lacus accumsan et viverra justo commodo.
Agreement Marked Active
Files to Distribute
File
Description
Filename.pdf
Lorem ipsum dolor si amet file description text
Save and Send Package
Save as Draft
Reviewer
Routing Sequence #
File Upload Access
Firstname Lastname
Research Technical Engineer & Applicant
<EMAIL_ADDRESS>000.000.0000
2
Firstname Lastname
Research Technical Engineer & Applicant
<EMAIL_ADDRESS>000.000.0000
ALT
Mary Meador
Research Technical Engineer & Applicant
<EMAIL_ADDRESS>000.000.0000
1
CC - S
Comments to Reviewer : Lorem ipsum dolor sit amet, consectetur adipiscing elit. Aenean euismod bibendum laoreet.
Comments
Comments to Reviewer : Lorem ipsum dolor sit amet, consectetur adipiscing elit. Aenean euismod bibendum laoreet.
Firstname Lastname
Research Technical Engineer & Applicant
<EMAIL_ADDRESS>000.000.0000
Auto
Cancel
Wireframe Notes
The wizard style of creating RPs allow the user to enter information in managable sections. The user can save the package at any step. The user will be able to review/edit all the details before starting routing.
Aftre review the user can either save the package or send the package to routing if so needed.


E-Card Generator
Enter details to generate your E-Card
What card do you want to gift ?
See templates
Copyright © 2021 -
Ronik Bhattacharjee


1. HTML are the major file types/documents on the web.
These are:
2.The standard format of an element is: <name>contents</name>
3.The element <a> is used to add a link to a word. An example is: Take a break!
4. Elements can be looked up online and need not be memorised.
5. Some elements have no text/context and do not need to be closed e.g. <img>
6.While there are several elemnts, the major thing to remeber is that they can be either inline or block.
7. Block element have a 'size' where inline elements are a continuious line of text


As a software engineer, I worked on building scalable backend services APIs. I love building things. While hard engineering problems are often intrinsically fun to tackle, I'm most attracted to solving real problems where I can take on on collaborative team leadership responsibilites, and gain experience with architecture and project management.
Our responsiblities involves building scalable restful web services which use spring boot microservices where we use Netflix Zuul as a api-gateway, Eureka as a service discovery, Rabbitmq as a message broker which digest messgae from queue. Sonarquebe used for static code analysis which inforce to use good practices . We use Elasticstack to build System Monitoring which help to monitor health of the system And we use Docker which made our deployment easy etc.
As a Intern, Our responsiblity involves to grow our tech stack via learning some awesome tools & technology such as spring boot framework, Maven, Git, MongoDb, or more which helps to build restful api.
Percentage: 75%
Percentage: 70%
Percentage: 81%
Apart from being a Software developer, I enjoy most of my time being outdoors playing games like Cricket, volly ball etc. I love to travel and explore new places.
When forced indoors, I'm watching movies, listening music, playing carrom, chess etc.


`
One of my favorite things about the Chrome web browser is how extensible it is. It seems like there is a Chrome plugin for just about everything you could ever possibly want.
But, have you ever wanted to create your own Chrome extension? Have you ever wondered how difficult the process would be or what it would entail? Well, it turns out it is super easy—probably a lot easier than you ever imagined.
In this tutorial I am going to show you how to create a basic Chrome extension in about 5 minutes—no joke!


x
Invite to Board
I'm working on this project in Trello and wanted to share it with you!
Send Invitation
[-]
Invite with Link
Create Link
Anyone with this link can join as board member


{% load static %}
Title
{% csrf_token %}
resultlab
Name of School:
{{ school_name }}
Class:
{{ classz }}
Current Term:
{{ term }}
Current Session:
{{ session }}
Date Prepared:
{{ date }}
S/N
REG NO
FULLNAME
{% for subject in subjects %}
{{ subject }}
{% endfor %}
OVERALL GRADING
{% for subject in subjects %}
score
pos
{% endfor %}
score
average
pos
attendance
remark


--- layout: page title: About header-img: "img/about-bg.png" ---
I am Cat Norris. I've had a long career in Tech for 41 years. I started my career as a User of one of the first CAD/CAM software package in the market and over the next 40 years had roles including System Engineer, Technical Manager, Product Manager, Enterprise Account Rep, and Global Alliance Manager small and large companies including Data General, Hewlett Packard, Silicon Graphics, Hitachi and NetApp.


??I
?
I
?
I
?
I
?
?
jjiiiHi
???
tm
II
1
II
1
?
y
?
11
?
?1
?
?1
?
?
?
?I
?
1
0
1
2
3
4
5
e
cm
7
8
9
10
copyright
reserved
The
New
York
Botanical
Garden
^^lKAGiÜD
NEW
YORK
BOTANICAL
GARDEN
01071765
Specimens
Collected
Under
the
Auspices
of
the
U.
S.
Department
of
Agriculture,
Forest
Service;
Tropical
Forest
Experiment
Station,
Rio
Piedras,
Puerto
Rico
Form
48-R.
8
TROPICAL
FOREST
HERBARIUM
13284
Botanical
name
:
pflinn
P.
(Accession
number
for
'
5L
____Washington
office)
Itonechino
_____
Determined
by____OET
f.
L.
Litt.-
Country:
Puerto
Rico
Political
division:
Bosque
Insular
ue
o
us
ua
8OO
LocaUty:
Wild
ED
Planted
?
Altitudel*QQ&nft.
Tree
CD
Shrub
EH
Vine
EH___________EH
HeightiLQ—iďifli.
D.
B.
hŪ.“?_Z.?_.ŪS§.
»
Flower
color,
odor;
fruit
color,
texture:
Abundance,
site,
slope,
r
vegetation
type,
etc.:
Dry
forest
Uses,
and
part
used;
locally
or
commercially:
Linociera
holdridr„i.
..............:
Other
notes:
Local
name:
Collector:
Elbert
L,
Little*
^T*
Date
of
collection:
»July
9,
1950
Collector’s
No.™.?™____
Legend -
Level of confidence that token is an accurately-transcribed word
extremely low
very low
low
undetermined
medium
high
very high


Exercise 2.4
; using consf since cons is reserved
(defn consf [x y]
(fn [m] (m x y)))
(defn car [z] (z (fn [p q] p)))
(defn cdr [z] (z (fn [p q] q)))
Testing (car (consf x y))
(car (fn [m] (m x y)))
((fn [m] (m x y)) (fn [p q] p))
((fn [p q] p) x y)
(x)
Testing (cdr (consf x y))
(cdr (fn [m] (m x y)))
((fn [m] (m x y)) (fn [p q] q))
((fn [p q] q) x y)
(y)
Exercise 2.5
Since 2 and 3 are prime, 2a and 3b are guaranteed to never have any common factors, other than 1.
Therefore the prime factorization of 2a3b can be evaluated for the number of its factors 2 and 3, a and b, respectively.
; using consf since cons is a reserved word
(defn pow
"return x^y where y is a non-negative integer"
[x y]
(loop [y y acc 1]
(if (= y 0)
acc
(recur (dec y) (* acc x)))))
(defn consf [a b] (* (pow 2 a) (pow 3 b)))
(defn powerFactor
"return power of prime factor p in n"
[n p]
(loop [n n acc 0]
(if (not= 0 (rem n p))
acc
(recur (/ n p) (inc acc)))))
(defn car [z] (powerFactor z 2))
(defn cdr [z] (powerFactor z 3))
Exercise 2.6
(def zero (fn [f] (fn [x] x)))
(defn add-1 [n] (fn [f] (fn [x] (f (n f) x))))
(def one (fn [f] (fn [x] (f x))))
(def two (fn [f] (fn [x] (f (f x)))))
(defn plus [a b]
(fn [f] (fn [x] ((a f) ((b f) x)))))
Exercise 2.7
(defstruct interval :lower-bound :upper-bound)
(defn make-interval [a b] (struct interval a b))
(def lower-bound (accessor interval :lower-bound))
(def upper-bound (accessor interval :upper-bound))
(defn add-interval [x y]
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
(defn mul-interval [x y]
(let [p1 (* (lower-bound x) (lower-bound y))
p2 (* (lower-bound x) (upper-bound y))
p3 (* (upper-bound x) (lower-bound y))
p4 (* (upper-bound x) (upper-bound y))]
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(defn div-interval [x y]
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))
Exercise 2.8
(defn sub-interval [x y]
(add-interval x
(make-interval (- (upper-bound y)) (- (lower-bound y)))))
Exercise 2.9
The width of the result of an arithmetic operation on intervals is one-halfth
the upper bound of the result minus the lower bound of the result.
Representing intervals algebraically,
(x1-w1, x1+w1) + (x2-w2, x2+w2) = (x1+x2-w1-w2, x1+x2+w1+w2)
The width of this result is w1+w2, obviously a function of w1 and w2.
Similarly for subtraction:
(x1-w1, x1+w1) - (x2-w2, x2+w2) = (x1-x2-w1-w2, x1-x2+w1+w2)
Again the width of this result is w1+w2, obviously a function of w1 and w2.
For multiplication, assuming x1, x2 >> 1 and w1, w2 << x1, x2,
but still greater than 1,
(x1-w1, x1+w1) * (x2-w2, x2+w2) = (x1x2 -w1x2 - w2x1 + w1w2, x1x2 + w1x2 + w2x1 + w1w2)
The width of this result is w1x2 + w2x1. Clearly this is not just a function
of w1 and w2. The same holds for division, which can be readily seen since
division can be reduced to multiplication.
(3, 5) * (5, 7) = (15, 35), width is w1x2 + w2x1, or 1*6 + 1*4 = 10
(5, 7) / (3, 5) = (1, 7/3), width is (w1x2 + w2x1)/((x2+w2)*(x2-w2))
= (3 + 5) / (4*3) = 8 / 12 = 2/3
Exercise 2.10
(defn div-interval [x y]
(if (and (< (lower-bound y) 0.0) (> (upper-bound y) 0.0))
(throw (IllegalArgumentException. "Divide by zero"))
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y))))))
Exercise 2.11
Through exhaustive analysis, the various possibilities for intervals
can be broken down into 9 cases. Describing the intervals as (L1, U1)
and (L2, U2), the pseudocode for the 9 cases follows:
if (L1 >= 0 && L2 >= 0)
then (L1*L2, U1*U2)
else if (U1 <= 0 && U2 <= 0)
then (U1*U2, L1*L2)
else if (L1 < 0 && L2 < 0 && U1 > 0 && U2 > 0)
then (MIN L1*U2 L2*U1, MAX L1*L2 U1*U2)
else if (L1 >= 0 && U2 <= 0)
then (U1*L2, L1*U2)
else if (L2 >= 0 && U1 <= 0)
then (L1*U2, U1*L2)
else if (L1 >= 0 && L2 < 0 && U2 > 0)
then (U1*L2, U1*U2)
else if (L1 < 0 && U1 > 0 && L2 >= 0)
then (L1*U2, U1*U2)
else if (U1 <= 0 && L2 < 0 && U2 > 0)
then (L1*U2, L1*L2)
else if (L1 < 0 && U1 > 0 && U2 <= 0)
then (U1*L2, L1*L2)
Double-checking that these cover all cases, number the cases A-I and
verifying that each possible scenario falls into a case:
-- -- B
-- -0 B
-- -+ H
-- 00 B
-- 0+ E
-- ++ E
-0 -- B
-0 -+ H
-0 00 B
-0 0+ E
-0 ++ E
-+ -- I
-+ -0 I
-+ -+ C
-+ 00 G
-+ 0+ G
-+ ++ G
00 -- B
00 -0 B
00 -+ F
00 00 A
00 0+ A
00 ++ A
0+ -- D
0+ -0 D
0+ -+ F
0+ 00 A
0+ 0+ A
0+ ++ A
++ -- D
++ -0 D
++ -+ F
++ 00 A
++ 0+ A
++ ++ A
Coding this, along with a tester to compare it to earlier mul-interval for various scenarios:
(defn mul-interval-new [x y]
(let [l1 (lower-bound x)
l2 (lower-bound y)
u1 (upper-bound x)
u2 (upper-bound y)]
(cond (and (>= l1 0) (>= l2 0)) (make-interval (* l1 l2) (* u1 u2))
(and (<= u1 0) (<= u2 0)) (make-interval (* u1 u2) (* l1 l2))
(and (< l1 0) (< l2 0) (> u1 0) (> u2 0)) (make-interval (min (* l1 u2) (* l2 u1)) (max (* l1 l2) (* u1 u2)))
(and (>= l1 0) (<= u2 0)) (make-interval (* u1 l2) (* l1 u2))
(and (>= l2 0) (<= u1 0)) (make-interval (* l1 u2) (* u1 l2))
(and (>= l1 0) (< l2 0) (> u2 0)) (make-interval (* u1 l2) (* u1 u2))
(and (< l1 0) (> u1 0) (>= l2 0)) (make-interval (* l1 u2) (* u1 u2))
(and (<= u1 0) (< l2 0) (> u2 0)) (make-interval (* l1 u2) (* l1 l2))
:else (make-interval (* u1 l2) (* l1 l2)))))
(defn cmpval [f1 f2 x y]
(let [i1 (f1 x y)
i2 (f2 x y)]
(if (not= i1 i2) (println "Failed for " x y))))
(defn testcases [f1 f2]
(cmpval f1 f2 (make-interval -10 10) (make-interval -10 10))
(cmpval f1 f2 (make-interval -10 0) (make-interval -10 10))
(cmpval f1 f2 (make-interval -10 -5) (make-interval -10 7))
(cmpval f1 f2 (make-interval 0 0) (make-interval 0 0))
(cmpval f1 f2 (make-interval 0 0) (make-interval -16 0))
(cmpval f1 f2 (make-interval 0 0) (make-interval -16 -12))
(cmpval f1 f2 (make-interval 0 0) (make-interval -13 7))
(cmpval f1 f2 (make-interval 0 0) (make-interval 0 3))
(cmpval f1 f2 (make-interval -7 -3) (make-interval 7 17))
(cmpval f1 f2 (make-interval -7 -2) (make-interval 0 21))
(cmpval f1 f2 (make-interval 3 7) (make-interval 0 0))
(cmpval f1 f2 (make-interval 4 6) (make-interval -7 -2))
(cmpval f1 f2 (make-interval 5 7) (make-interval -13 0))
(cmpval f1 f2 (make-interval 4 8) (make-interval -12 17))
(cmpval f1 f2 (make-interval 7 13) (make-interval 7 13))
(cmpval f1 f2 (make-interval 7 11) (make-interval 0 21))
(cmpval f1 f2 (make-interval -12 7) (make-interval -13 1))
(cmpval f1 f2 (make-interval -17 2) (make-interval -5 20)))
Exercise 2.12
(defn abs [x] (if (< x 0) (- x) x))
(defn make-center-width [c w]
(make-interval (- c w) (+ c w)))
(defn center [i] (/ (+ (lower-bound i) (upper-bound i)) 2))
(defn width [i] (/ (- (upper-bound i) (lower-bound i)) 2))
(defn make-center-percent
"Interval constructor taking a center point and percent tolerance"
[center pct-tol]
(let [width (abs (* center pct-tol))]
(make-interval (- center width) (+ center width))))
(defn percent [i]
(/ (width i) (center i)))
Exercise 2.13
Intervals can be expressed as c +/- tc, where c is center and t is a tolerance
percentage. Assuming all numbers are positive, product of two intervals,
c1 +/- t*c1 and c2 +/- t*c2 = (c1*(1-t1) * c2*(1-t2), c1*(1+t1) * c2(1+t2))
= (c1*c2 * (1-t1)(1-t2), c1*c2 * (1+t1)(1+t2))
= (c1*c2 * (1 - t1 - t2 - t1*t2), c1*c2 * (1 + t1 + t2 + t1*t2))
So tolerance of the product interval = t1 + t2 + t1*t2
For small values of t1 and t2, this is approximately equal to t1+t2 since
t1*t2 will be quite small indeed.
Exercise 2.14
R1R2 / (R1+R2) = (RL1,RH1)(RL2,RH2) / ((RL1,RH1) + (RL2,RH2))
= (RL1*RL2,RH1*RH2) / (RL1+RL2,RH1+RH2)
= (RL1*RL2,RH1*RH2) * (1/(RH1+RH2),1/(RL1+RL2)
= (RL1*RL2/(RH1+RH2),RH1*RH2/(RL1+RL2))
1 / (1/R1 + 1/R2)
= (1,1) / ((1,1) / (RL1,RH1) + (1,1) / (RL2,RH2))
= (1,1) / ((1,1)*(1/RH1,1/RL1) + (1,1)*(1/RH2,1/RL1))
= (1,1) / ((1/RH1,1/RL1) + (1/RH2,1/RL2))
= (1,1) / (1/RH1 + 1/RH2, 1/RL1 + 1/RL2)
= (1,1) / (RH1+RH2 / (RH1*RH2), RL1+RL2 / (RL1*RL2))
= (1,1) * ((RL1*RL2)/(RL1+RL2),(RH1*RH2)/(RH1+RH2))
= ((RL1*RL2)/(RL1+RL2),(RH1*RH2)/(RH1+RH2))
These 2 versions differ in the denominators, so they yield differing
results in general.
Computing expressions like A/A having the same non-zero-width interval variable occurring more than once tends to yield incorrect results. Obviously the correct answer for A/A ought to be (1,1), but instead we end up with a non-zero-width interval, effectively treating the two occurrences of A as independent variables, that are allowed to take on different values.
user=> (def a (make-center-percent 4.2 0.1))
#'user/a
user=> (div-interval a a)
{:lower-bound 0.8181818181818182, :upper-bound 1.222222222222222}
user=> (percent (div-interval a a))
0.19801980198019795
user=> (def b (make-center-percent 13 0.7))
#'user/b
user=> (percent (div-interval b b))
0.9395973154362415
user=> (div-interval a b)
{:lower-bound 0.17104072398190046, :upper-bound 1.1846153846153846}
user=> (percent (div-interval a b))
0.7476635514018691
user=> (center (div-interval a b))
0.6778280542986426
user=>
Exercise 2.15
Yes, Eva is correct: expressions with the same uncertain interval variable occurring more than once add more uncertainty into the final results (looser error bounds) than is actually warranted. We see this with A/A, which ought to have a certain value of 1, but instead accumulates uncertainty. par2 is indeed a "better" program from this perspective, since it does not suffer from this deficiency and should calculate tighter bounds than par1.
Exercise 2.16
As has been discussed in exercises 2.14 and 2.15, an algebraic expression containing an uncertain variable more than once can return erroneous results, by erroneously treating each occurrence of the variable as independent variables. An algebraic equivalent expression that doesn't contain this duplicate variable won't suffer from this, and therefore will return a different answer.
For constructing an interval-arithmetic package that does not have this shortcoming, one approach could lock the multiple occurrences of the same variable together. It still appears that only the endpoints of each interval need be considered for computing the overall answer. But the simplest implementation would still consider all permutations of interval endpoints, and return the interval determined by the overall minimum and maximum. This may be difficult to achieve, but seems possible.
Problems arise in cases where "literal" intervals defined with make-interval are used in lieu of variables. Multiple occurrences of identical literal intervals may be involved in an expression. It is not possible to know whether these identical intervals correspond to the same measured value (i.e., should be treated as locked together), or whether they happen to be identical via coincidence, and hence should be correctly treated as independent. The safest thing to do here is to always assume these literal intervals are independent, but this assumption may not always align with the user's assumptions. In these cases, the new interval arithmetic package will still suffer from this "shortcoming".
We have not learned how to distinguish between a literal expression and a variable reference to an expression, so it does not seem possible to devise an interval arithmetic package that performs as we would want it to.
Exercise 2.17
(defn last-pair
"Return list containing last element of specified sequence"
[seq]
(if (empty? (rest seq))
seq
(recur (rest seq))))
Exercise 2.18
; defining reverse for Exercise 2.18 even though it's already built-in
(defn reverse-seq
"Return reverse of specified sequence"
[seq]
(defn revR [acc seq]
(if (empty? seq)
acc
(recur (cons (first seq) acc) (rest seq))))
(revR () seq))
Exercise 2.19
(def first-denomination first)
(def except-first-denomination rest)
(def no-more? empty?)
(defn cc
"Return # of ways to count change for the specified amount using specified coins"
[amount coin-values]
(cond (= amount 0) 1
(or (< amount 0) (no-more? coin-values)) 0
:else (+ (cc amount
(except-first-denomination coin-values))
(cc (- amount
(first-denomination coin-values))
coin-values))))
Order of coin-values does not affect the answer produced by cc because cc does not regard coin-values as an ordered list (e.g., aborting consumption of list when a certain denomination is reached) -- it always consumes the list until amount is exhausted or the list itself is exhausted.
Exercise 2.20
(defn same-parity
"Return list containing all arguments that have the same even/odd parity as the first argument"
[& args]
(filter (fn [x] (= (even? x) (even? (first args)))) args))
Exercise 2.21
(defn square-list1 [items]
(if (empty? items)
()
(let [frst (first items)]
(cons (* frst frst) (square-list1 (rest items))))))
(defn square-list2 [items]
(map (fn [x] (* x x)) items))
Exercise 2.22
Louis' iterative version of square-list produces the answer list in the reverse order because on each iteration it peels one element from the left side of the input list and prepends a corresponding element onto the front of the output list. So as the input list is read left-to-right, the output list is built right-to-left.
Reversing the order of the arguments to cons doesn't solve the problem. Cons expects its first argument to be of type element and the second argument to be of type sequence[element], so you generally cannot switch arguments around and even if the type system lets you do it, it would yield nonsensical results. The correct fix is to either not use cons to build up the output list (appending to end of list instead), or to do it as a linear recursive process, or else simply reverse the output list as a final step.
Exercise 2.23
(defn for-each
"Apply f to each element in specified sequence, discarding results"
[f seq]
(if (empty? seq)
()
(do
(f (first seq))
(recur f (rest seq)))))
Exercise 2.24
(list 1 (list 2 (list 3 4))) would be printed as
(1 (2 (3 4))) by the interpreter. ASCII-art box-and-pointer structure is
+-+-+ +-+-+
|.|.-->|.|/|
+|+-+ +|+-+
| |
V V
1 +-+-+ +-+-+
|.|.-->|.|/|
+|+-+ +|+-+
| |
V V
2 +-+-+ +-+-+
|.|.-->|.|/|
+|+-+ +|+-+
| |
V V
3 4
And viewed as a tree,
+--> 1
|
+--+--> 2
|
+--+--> 3
|
+--> 4
Exercise 2.25
(car (cdr (car (cdr (cdr x))))) (or cadaddr x) will return 7 when x is (1 3 (5 7) 9)
In Clojure this would be written
(first (rest (first (rest (rest x)))))
(car (car x)) (or caar x) will return 7 when x is ((7))
In Clojure this would be written
(first (first x))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr x)))))))))))) returns 7 when x is (1 (2 (3 (4 (5 (6 7))))))
In Clojure this would be written
(first (rest (first (rest (first (rest (first (rest (first (rest (first (rest x))))))))))))
Exercise 2.26
(append x y) would print (1 2 3 4 5 6)
(cons x y) would print ((1 2 3) 4 5 6)
(list x y) would print ((1 2 3) (4 5 6))
Exercise 2.27
; deep-reverse-seq reverses all sub-sequences as well as outer sequence
(defn deep-reverse-seq
"Return deep reverse of specified sequence"
[seq]
(defn revR [acc seq]
(if (empty? seq)
acc
(let [frstEl (first seq)]
(recur (cons (if (seq? frstEl) (deep-reverse-seq frstEl) frstEl) acc) (rest seq)))))
(revR () seq))
Exercise 2.28
(defn fringe
"return list of leaves of tree in left-to-right order"
[tree]
(if (seq? tree)
(if (empty? tree)
()
(concat (fringe (first tree)) (fringe (rest tree))))
(list tree)))
Exercise 2.29
(defn make-mobile
"Make binary mobile, based on left and right branch"
[left right]
(list left right))
(defn make-branch
"Make mobile branch based upon its length and structure"
[len struc]
(list len struc))
(defn left-branch
"return left branch of binary mobile"
[mobile]
(first mobile))
(defn right-branch
"return right branch of binary mobile"
[mobile]
(first (rest mobile)))
(defn branch-length
"return length of a binary mobile branch"
[branch]
(first branch))
(defn branch-structure
"return structure associated with a binary mobile branch"
[branch]
(first (rest branch)))
(defn is-simple-weight?
"return whether structure is a simple weight (versus a mobile)"
[struc]
(not (seq? struc)))
(defn total-weight
"return total weight of a binary mobile"
[mobile]
(defn total-branch-weight
"return total weight associated with a branch, ignoring arm weight"
[branch]
(let [struc (branch-structure branch)]
(if (is-simple-weight? struc)
struc
(total-weight struc))))
(+ (total-branch-weight (left-branch mobile))
(total-branch-weight (right-branch mobile))))
(defn balanced?
"return whether specified binary mobile is balanced"
[mobile]
(let [leftbranch (left-branch mobile)
rightbranch (right-branch mobile)
leftstruc (branch-structure leftbranch)
rightstruc (branch-structure rightbranch)
leftweight (if (is-simple-weight? leftstruc)
leftstruc
(total-weight leftstruc))
rightweight (if (is-simple-weight? rightstruc)
rightstruc
(total-weight rightstruc))
leftlen (branch-length leftbranch)
rightlen (branch-length rightbranch)
lefttorque (* leftlen leftweight)
righttorque (* rightlen rightweight)
leftbalanced (if (is-simple-weight? leftstruc)
true
(balanced? leftstruc))
rightbalanced (if (is-simple-weight? rightstruc)
true
(balanced? rightstruc))]
(and (= lefttorque righttorque) leftbalanced rightbalanced)))
If we change the representation, then besides the constructors
make-mobile and make-branch changing, we need to change our "primitive"
accessors: left-branch, right-branch, branch-length, branch-structure,
and is-simple-weight?
Clojure doesn't directly support cons cells, but rather deals in sequences, so part d cannot be directly translated into Clojure using cons cells.
Exercise 2.30
(defn square-tree1
"return tree (nested list) structure similar to input but with numbers squared"
[tree]
(cond (not (seq? tree)) (* tree tree)
(empty? tree) ()
:else (let [frst (first tree)]
(cons (square-tree1 frst) (square-tree1 (rest tree))))))
(defn square-tree2
"return tree (nested list) structure similar to input but with numbers squared"
[tree]
(map (fn [n] (if (seq? n) (square-tree2 n) (* n n))) tree))
Exercise 2.31
(defn tree-map
"apply a function to every element in a tree (nested list)"
[f tree]
(map (fn [n] (if (seq? n) (tree-map f n) (f n))) tree))
Exercise 2.32
(defn subsets
"return set of all subsets (powerset) of s"
[s]
(if (empty? s)
(list ())
(let [rst (subsets (rest s))]
(concat rst (map (fn [x] (cons (first s) x)) rst)))))
This works because powerset can be implemented recursively (or via induction) by considering the base case of an empty list, in which case the powerset is (()), and the non-empty case. In the non-empty case, we separate the first element and the remainder of the set; we generate the powerset of the remainder of the set and then for each element of this remainder powerset, we include in the result both this element and this element with the first element prepended.
Another way of thinking of it is by noticing that the size of the powerset is always equal to 2^n, where n is the size of the input set. This makes sense since each element is included in half the elements in the powerset result. If you consider each element in the input set to correspond to a binary digit position, then looking at the binary expansion of 0..2^n, you build the powerset by selecting the input elements corresponding to the 1 digits for each 0..2^n value.
The anonymous function could be dispensed with if Clojure allowed partial application (e.g., passing (cons (first s)) to map).
Exercise 2.33
; implement foldr (aka reduce)
(defn accumulate
"accumulate value by applying binary operator to accumulator w/ each element"
[op initial sequence]
(if (empty? sequence)
initial
(op (first sequence)
(accumulate op initial (rest sequence)))))
; named map-seq since name map is reserved
(defn map-seq [p sequence]
(accumulate (fn [x y] (cons (p x) y)) () sequence))
(defn append [seq1 seq2]
(accumulate cons seq2 seq1))
(defn length [sequence]
(accumulate (fn [x y] (inc y)) 0 sequence))
Exercise 2.34
(defn horner-eval
"Evaluate polynomial using Horner's rule"
[x coefficient-sequence]
(accumulate (fn [this-coeff higher-terms] (+ (* x higher-terms) this-coeff))
0
coefficient-sequence))
Exercise 2.35
(defn count-leaves
"return count of leaves in tree (nested list)"
[t]
(accumulate (fn [x y] (+ y (if (seq? x) (count-leaves x) 1)))
0 t))
I ran into type conversion problems trying to apply count-leaves with map. If you must use map, you can add a dummy map applying the identity function.
Exercise 2.36
(defn accumulate-n
"Accumulate n values, folding using nth element of each specified sequence"
[op init seqs]
(if (empty? (first seqs))
()
(cons (accumulate op init (map first seqs))
(accumulate-n op init (map rest seqs)))))
Exercise 2.37
(defn dot-product
"return dot product of two vectors"
[v w]
(accumulate + 0 (map * v w)))
(defn matrix-star-vector
"multiply matrix times vector"
[m v]
(map (fn [mi] (accumulate + 0 (map * mi v))) m))
(defn transpose
"transpose rows and columns in matrix"
[mat]
(accumulate-n cons () mat))
(defn matrix-star-matrix
"multiply matrix by matrix"
[m n]
(let [cols (transpose n)]
(map (fn [mi] (map (fn [nj] (dot-product mi nj)) cols)) m)))
Exercise 2.38
(defn fold-right
"fold from the right-hand side (same as accumulate)"
[op initial sequence]
(if (empty? sequence)
initial
(op (first sequence)
(fold-right op initial (rest sequence)))))
(defn fold-left
"fold from left-hand side"
[op initial sequence]
(defn iter [result rst]
(if (empty? rst)
result
(iter (op result (first rst))
(rest rst))))
(iter initial sequence))
(fold-right / 1 (list 1 2 3)) equals 3/2
(fold-left / 1 (list 1 2 3)) equals 1/6
(fold-right list () (list 1 2 3)) equals (1 (2 (3 ())))
(fold-left list () (list 1 2 3)) equals (((() 1) 2) 3)
op must be an associative and commutative operation in order to guarantee
that fold-left and fold-right produce the same values for any sequence.
Exercise 2.39
; use nested fold-right
(defn reverse1
"reverse sequence using fold-right"
[sequence]
(fold-right (fn [x y] (fold-right cons (list x) y)) () sequence))
; using append rather than nested fold-right
(defn reverse1a
"reverse sequence using fold-right"
[sequence]
(fold-right (fn [x y] (append y (list x))) () sequence))
(defn reverse2
"reverse sequence using fold-left"
[sequence]
(fold-left (fn [x y] (cons y x)) () sequence))
Exercise 2.40
(defn enumerate-interval [low high]
(range low (inc high)))
(defn unique-pairs
"return sequence of unique pairs (i,j) with 1 <= j < i <= n"
[n]
(for [i (range 1 (inc n)) j (range 1 i)] (list i j)))
(defn flatmap
"combined map with folding (using append)"
[proc seq]
(accumulate append () (map proc seq)))
(defn make-pair-sum
[pair]
(let [fst (first pair) snd (first (rest pair))]
(list fst snd (+ fst snd))))
(defn next-divisor
"return next divisor value to test for find-divisor"
[n]
(if (= n 2) 3 (+ n 2)))
; find smallest divisor of n
(defn remainder [a b] (mod a b))
(defn square [n] (* n n))
(defn divides? [a b]
(= (remainder b a) 0))
(defn find-divisor [n test-divisor]
(loop [n n test-divisor test-divisor]
(cond (> (square test-divisor) n) n
(divides? test-divisor n) test-divisor
:else (recur n (next-divisor test-divisor)))))
(defn smallest-divisor [n]
(find-divisor n 2))
(defn prime? [n]
(= n (smallest-divisor n)))
(defn prime-sum? [pair]
(prime? (+ (first pair) (first (rest pair)))))
(defn prime-sum-pairs
"return all pairs of unique integers up to n that add up to a prime"
[n]
(map make-pair-sum
(filter prime-sum? (unique-pairs n))))
Exercise 2.41
(defn ex2_41
"return ordered triples of distinct positive ints i,j,k <= n that sum to s"
[n s]
(for [i (range 1 (inc n)) j (range 1 i) k (range 1 j) :while (= s (+ i j k))]
(list i j k)))
Exercise 2.42
(defn abs [n] (if (< n 0) (- n) n))
(defn enumerate-interval
[low high]
(range low (inc high)))
(defn flatmap
"combined map with folding (using append)"
[proc seq]
(accumulate append () (map proc seq)))
(def empty-board ())
(defn adjoin-position
"return board with queen added at specified row, col"
[row col board]
(cons (list row col) board))
(defn safe?
"return whether queen in kth column is safe w/ respect to positions"
[col positions]
(defn safeR [p b]
(let [position (first (filter (fn [n] <= col (first (rest n))) positions))
row (first position)
prow (first p)
pcol (first (rest p))]
(cond (not b) false
(= col pcol) b
(= row prow) false
(= (abs (- row prow)) (abs (- col pcol))) false
:else b)))
(accumulate safeR true positions))
(defn queens
"solve the N queens problem for a board of specified NxN size"
[board-size]
(defn queen-cols [k]
(if (= k 0)
(list empty-board)
(filter
(fn [positions] (safe? k positions))
(flatmap
(fn [rest-of-queens]
(map (fn [new-row] (adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (dec k))))))
(queen-cols board-size))
Exercise 2.43
queen-cols is a relatively expensive, recursive function. In the original implementation, each call of queen-cols would recursively once into queen-cols with the next lower value of k. By transposing the nested mappings, Louis' implementation is calling queen-cols N times, rather than once, from each call, where N is equal to the board size.
Since this effective multiplication of runtime by N occurs at each level, it becomes an exponential increase in runtime, changing the estimated runtime from T to T * NN.
Exercise 2.44
(defn right-split
"recursively split painter to the right, n times"
[painter n]
(if (= n 0)
painter
(let [smaller (right-split painter (dec n))]
(beside painter (below smaller smaller)))))
(defn up-split
"recursively split painter upwards, n times"
[painter n]
(if (= n 0)
painter
(let [smaller (up-split painter (dec n))]
(below painter (beside smaller smaller)))))
Exercise 2.45
(defn split
"general painter split defined in terms of an inner and outer operation"
[outer inner]
(defn splitR [painter n]
(if (= n 0)
painter
(let [smaller (splitR painter (dec n))]
(outer painter (inner smaller smaller)))))
splitR)
Exercise 2.46
(defn make-vect [x y] [x y])
(def xcor-vect first)
(def ycor-vect second)
(defn add-vect
"add two vectors"
[v1 v2]
(let [x1 (xcor-vect v1) x2 (xcor-vect v2)
y1 (ycor-vect v1) y2 (ycor-vect v2)]
(make-vect (+ x1 x2) (+ y1 y2))))
(defn sub-vect
"subtract vector v2 from vector v1"
[v1 v2]
(let [x1 (xcor-vect v1) x2 (xcor-vect v2)
y1 (ycor-vect v1) y2 (ycor-vect v2)]
(make-vect (- x1 x2) (- y1 y2))))
(defn scale-vect
"multiply vector by a scalar"
[s v]
(make-vect (* s (xcor-vect v)) (* s (ycor-vect v))))
Exercise 2.47
Clojure does not use cons cells, so the second constructor cannot work here. Instead I will use a struct.
(defn make-frame1
"make frame, using a list"
[origin edge1 edge2]
(list origin edge1 edge2))
(def origin-frame1 first)
(def edge1-frame1 second)
(defn edge2-frame1 [f] (nth f 2))
(defstruct frame :origin :edge1 :edge2)
(defn make-frame2
"make frame, using a struct"
[origin edge1 edge2]
(struct frame origin edge1 edge2))
(def origin-frame2 (accessor frame :origin))
(def edge1-frame2 (accessor frame :edge1))
(def edge2-frame2 (accessor frame :edge2))
Exercise 2.48
(defstruct linesegment :vect-to-origin :vect-to-endpoint)
(defn make-segment
"make line segment from two vectors"
[vOrigin vEnd]
(struct linesegment vOrigin vEnd))
(def start-segment (accessor linesegment :vect-to-origin))
(defn end-segment
"return endpoint (vector) of a line segment"
[ls]
(add-vect (:vect-to-origin ls) (:vect-to-endpoint ls)))
Exercise 2.49
(defn for-each
"Apply f to each element in specified sequence, discarding results"
[f seq]
(if (empty? seq)
()
(do
(f (first seq))
(recur f (rest seq)))))
(defn segments->painter
"from list of segments, create a painter procedure that paints into a frame"
[segment-list]
(fn [frame]
(for-each
(fn [segment]
(draw-line
((frame-coord-map frame) (start-segment segment))
((frame-coord-map frame) (end-segment segment))))
segment-list)))
(def outline-painter
(segments->painter (list (make-segment (make-vect 0 0) (make-vect 0 1))
(make-segment (make-vect 0 1) (make-vect 1 0))
(make-segment (make-vect 1 1) (make-vect 0 -1))
(make-segment (make-vect 1 0) (make-vect -1 0)))))
(def x-painter
(segments->painter (list (make-segment (make-vect 0 0) (make-vect 1 1))
(make-segment (make-vect 0 1) (make-vect 1 -1)))))
(def diamond-painter
(segments->painter (list (make-segment (make-vect 0 0.5) (make-vect 0.5 0.5))
(make-segment (make-vect 0.5 1) (make-vect 0.5 -0.5))
(make-segment (make-vect 1 0.5) (make-vect -0.5 -0.5))
(make-segment (make-vect 0.5 0) (make-vect -0.5 0.5)))))
(def wave-painter
(segments->painter (list (make-segment (make-vect 0 0.85) (make-vect 0.15 -0.25))
(make-segment (make-vect 0.15 0.6) (make-vect 0.15 0.05))
(make-segment (make-vect 0.3 0.65) (make-vect 0.1 0))
(make-segment (make-vect 0.4 0.65) (make-vect -0.05 0.2))
(make-segment (make-vect 0.35 0.85) (make-vect 0.05 0.15))
(make-segment (make-vect 0.6 1) (make-vect 0.05 -0.15))
(make-segment (make-vect 0.65 0.85) (make-vect -0.05 -0.2))
(make-segment (make-vect 0.6 0.65) (make-vect 0.15 0))
(make-segment (make-vect 0.75 0.65) (make-vect 0.25 -0.3))
(make-segment (make-vect 1 0.15) (make-vect -0.4 0.35))
(make-segment (make-vect 0.6 0.5) (make-vect 0.15 -0.5))
(make-segment (make-vect 0.6 0) (make-vect -0.1 0.3))
(make-segment (make-vect 0.5 0.3) (make-vect -0.1 -0.3))
(make-segment (make-vect 0.25 0) (make-vect 0.1 0.5))
(make-segment (make-vect 0.35 0.5) (make-vect -0.05 0.1))
(make-segment (make-vect 0.3 0.6) (make-vect -0.15 -0.2))
(make-segment (make-vect 0.15 0.4) (make-vect -0.15 0.25)))))
Exercise 2.50
(defn transform-painter
"transform painter by mapping into a different frame"
[painter origin corner1 corner2]
(fn [frame]
(let [m (frame-coord-map frame) new-origin (m origin)]
(painter
(make-frame new-origin
(sub-vect (m corner1) new-origin)
(sub-vect (m corner2) new-origin))))))
(defn flip-horiz
"flip painter horizontally"
[painter]
(transform-painter painter
(make-vect 1.0 0.0)
(make-vect 0.0 0.0)
(make-vect 1.0 1.0)))
(defn rotate180
"rotate (square) painter 180 degrees counterclockwise"
[painter]
(transform-painter painter
(make-vect 1.0 1.0)
(make-vect 0.0 1.0)
(make-vect 1.0 0.0)))
(defn rotate270
"rotate (square) painter 270 degrees counterclockwise"
[painter]
(transform-painter painter
(make-vect 0.0 1.0)
(make-vect 0.0 0.0)
(make-vect 1.0 1.0)))
Exercise 2.51
(defn below1
"create composite painter out of 2 other painters, painting first below 2nd"
[painterB painterT]
(let [split-point (make-vect 0.0 0.5)
paint-top (transform-painter painterT
split-point
(make-vect 1.0 0.0)
(make-vect 0.0 1.0))
paint-bottom (transform-painter painterB
(make-vect 0.0 0.0)
(make-vect 1.0 0.0)
split-point)]
(fn [frame]
(paint-top frame)
(paint-bottom frame))))
(defn below2
"create composite painter out of 2 other painters, painting first below 2nd"
[painterB painterT]
(rotate90 (beside (rotate270 painterB) (rotate270 painterT))))
Exercise 2.52
(defn corner-split
[painter n]
(if (= n 0)
painter
(let [up (up-split painter (dec n))
right (right-split painter (dec n))
top-left (beside up up)
bottom-right (below right right)
corner (corner-split painter (dec n))]
(beside (below painter top-left)
(below bottom-right corner)))))
(defn flip-vert
[painter]
(transform-painter painter
(make-vect 0.0 1.0)
(make-vect 1.0 1.0)
(make-vect 0.0 0.0)))
(defn flip-horiz
[painter]
(transform-painter painter
(make-vect 1.0 0.0)
(make-vect 0.0 0.0)
(make-vect 1.1 1.1)))
(def wave-with-smile-painter
(segments->painter (list (make-segment (make-vect 0 0.85) (make-vect 0.15 -0.25))
(make-segment (make-vect 0.15 0.6) (make-vect 0.15 0.05))
(make-segment (make-vect 0.3 0.65) (make-vect 0.1 0))
(make-segment (make-vect 0.4 0.65) (make-vect -0.05 0.2))
(make-segment (make-vect 0.35 0.85) (make-vect 0.05 0.15))
(make-segment (make-vect 0.6 1) (make-vect 0.05 -0.15))
(make-segment (make-vect 0.65 0.85) (make-vect -0.05 -0.2))
(make-segment (make-vect 0.6 0.65) (make-vect 0.15 0))
(make-segment (make-vect 0.75 0.65) (make-vect 0.25 -0.3))
(make-segment (make-vect 1 0.15) (make-vect -0.4 0.35))
(make-segment (make-vect 0.6 0.5) (make-vect 0.15 -0.5))
(make-segment (make-vect 0.6 0) (make-vect -0.1 0.3))
(make-segment (make-vect 0.5 0.3) (make-vect -0.1 -0.3))
(make-segment (make-vect 0.25 0) (make-vect 0.1 0.5))
(make-segment (make-vect 0.35 0.5) (make-vect -0.05 0.1))
(make-segment (make-vect 0.3 0.6) (make-vect -0.15 -0.2))
(make-segment (make-vect 0.15 0.4) (make-vect -0.15 0.25))
(make-segment (make-vect 0.4 0.85) (make-vect 0.05 -0.1))
(make-segment (make-vect 0.45 0.75) (make-vect 0.1 0))
(make-segment (make-vect 0.55 0.75) (make-vect 0.05 0.1)))))
(defn corner-split-new
"corner split, revised for exercise 2.52"
[painter n]
(if (= n 0)
painter
(let [up (up-split painter (dec n))
right (right-split painter (dec n))
corner (corner-split painter (dec n))]
(beside (below painter up)
(below right corner)))))
(defn square-of-four
[tl tr bl br]
(fn [painter]
(let [top (beside (tl painter) (tr painter))
bottom (beside (bl painter) (br painter))]
(below bottom top))))
(defn square-limit-new
"square-limit, revised for exercise 2.52 to make Mr. Rogers look out corners"
[painter n]
(let [combine4 (square-of-four flip-vert rotate180
identity flip-horiz)]
(combine4 (corner-split painter n))))
Exercise 2.53
(defn memq
[item x]
(cond (empty? x) false
(= item (first x)) x
:else (memq item (rest x))))
(list 'a 'b 'c) causes interpreter to print: (a b c)
(list (list 'george)) causes interpreter to print: ((george))
(rest '((x1 x2) (y1 y2))) causes interpreter to print: ((y1 y2))
(second '((x1 x2) (y1 y2))) causes interpret to print: (y1 y2)
(pair? (car '(a short list))) cannot be directly translated to Clojure
(memq 'red '((red shoes) (blue socks))) causes interpreter to print: false
(memq 'red '(red shoes blue socks)) causes interpreter to print: (red shoes blue socks)
Exercise 2.54
(defn equal?
[a b]
(let [firsta (first a) firstb (first b)]
(cond (and (empty? a) (empty? b)) true
(or (empty? a) (empty? b)) false
(and (list? firsta) (list? firstb))
(and (= (first firsta) (first firstb))
(equal? (rest firsta) (rest firstb)))
(or (list? firsta) (list? firstb)) false
:else (and (= firsta firstb) (equal? (rest a) (rest b))))))
Exercise 2.55
(first ''abracadabra) is interpreted by the interpreter as
(first (quote (quote abracadabra)))
or, alternately
(first '(quote abracadabra))
So first is applied to the quoted list, and of course returns the first atom, quote.
Exercise 2.56
(def variable? symbol?)
(defn same-variable? [v1 v2]
(and variable? v1) (variable? v2) (= v1 v2))
(defn =number? [exp num] (and (number? exp) (= exp num)))
(defn make-sum
[a1 a2]
(cond (=number? a1 0) a2
(=number? a2 0) a1
(and (number? a1) (number? a2)) (+ a1 a2)
:else (list '+ a1 a2)))
(defn make-product
[m1 m2]
(cond (or (=number? m1 0) (=number? m2 0)) 0
(=number? m1 1) m2
(=number? m2 1) m1
(and (number? m1) (number? m2)) (* m1 m2)
:else (list '* m1 m2)))
(defn sum? [x] (and (list? x) (= (first x) '+)))
(def addend second)
(defn augend [s] (nth s 2))
(defn product? [x] (and (list? x) (= (first x) '*)))
(def multiplier second)
(defn multiplicand [p] (nth p 2))
(defn error [msg & rst] (throw (new Exception (str msg (print-str rst)))))
(defn exponentiation? [x] (and (list? x) (= (first x) '**)))
(defn make-exponentiation
[b e]
(cond (=number? e 0) 1
(=number? e 1) b
:else (list '** b e)))
(def base second)
(defn exponent [x] (nth x 2))
(defn deriv
"Perform symbolic differentiation of expression, returning derivative w/ respect to specified var"
[exp var]
(cond (number? exp) 0
(variable? exp) (if (same-variable? exp var) 1 0)
(sum? exp) (make-sum (deriv (addend exp) var)
(deriv (augend exp) var))
(product? exp) (make-sum (make-product (multiplier exp)
(deriv (multiplicand exp) var))
(make-product (deriv (multiplier exp) var)
(multiplicand exp)))
(exponentiation? exp)
(make-product (make-product (exponent exp)
(make-exponentiation (base exp) (make-sum (exponent exp) -1)))
(deriv (base exp) var))
:else (error "unknown expression type -- DERIV" exp)))
For the following couple exercises, assuming we don't have exponentiation, but just addition and multiplication, as the text seems to imply.
Exercise 2.57
(defn make-sum-simple
[a1 a2]
(cond (=number? a1 0) a2
(=number? a2 0) a1
(and (number? a1) (number? a2)) (+ a1 a2)
:else (list '+ a1 a2)))
(defn make-sum
[& rst]
(defn make-sumR
[l]
(cond (= 2 (length l)) (make-sum-simple (first l) (second l))
:otherwise (make-sum-simple (first l) (make-sumR (rest l)))))
(make-sumR rst))
(defn make-product-simple
[m1 m2]
(cond (or (=number? m1 0) (=number? m2 0)) 0
(=number? m1 1) m2
(=number? m2 1) m1
(and (number? m1) (number? m2)) (* m1 m2)
:else (list '* m1 m2)))
(defn make-product
[& rst]
(defn make-productR
[l]
(cond (= 2 (length l)) (make-product-simple (first l) (second l))
:otherwise (make-product-simple (first l) (make-productR (rest l)))))
(make-productR rst))
(defn sum? [x] (and (seq? x) (= (first x) '+)))
(def addend second)
(defn augend [x] (if (> (length x) 3) (cons '+ (drop 2 x)) (nth x 2)))
(defn product? [x] (and (seq? x) (= (first x) '*)))
(def multiplier second)
(defn multiplicand [x] (if (> (length x) 3) (cons '* (drop 2 x)) (nth x 2)))
Exercise 2.58
a.
(defn make-sum
[a1 a2]
(cond (=number? a1 0) a2
(=number? a2 0) a1
(and (number? a1) (number? a2)) (+ a1 a2)
:else (list a1 '+ a2)))
(defn make-product
[m1 m2]
(cond (or (=number? m1 0) (=number? m2 0)) 0
(=number? m1 1) m2
(=number? m2 1) m1
(and (number? m1) (number? m2)) (* m1 m2)
:else (list m1 '* m2)))
(defn sum? [x] (and (seq? x) (= (second x) '+)))
(def addend first)
(defn augend [x] (nth x 2))
(defn product? [x] (and (seq? x) (= (second x) '*)))
(def multiplier first)
(defn multiplicand [x] (nth x 2))
part b:
(defn make-sum-simple
[a1 a2]
(cond (=number? a1 0) a2
(=number? a2 0) a1
(and (number? a1) (number? a2)) (+ a1 a2)
:else (list a1 '+ a2)))
(defn make-sum
[& rst]
(defn make-sumR
[l]
(cond (= 2 (length l)) (make-sum-simple (first l) (second l))
:otherwise (make-sum-simple (first l) (make-sumR (rest l)))))
(make-sumR rst))
(defn make-product-simple
[m1 m2]
(cond (or (=number? m1 0) (=number? m2 0)) 0
(=number? m1 1) m2
(=number? m2 1) m1
(and (number? m1) (number? m2)) (* m1 m2)
:else (list m1 '* m2)))
(defn make-product
[& rst]
(defn make-productR
[l]
(cond (= 2 (length l)) (make-product-simple (first l) (second l))
:otherwise (make-product-simple (first l) (make-productR (rest l)))))
(make-productR rst))
(defn sum? [x] (and (seq? x) (> (length x) 2) (or (= (second x) '+) (sum? (drop 2 x)))))
(defn addend [x] (if (= (second x) '+) (first x) (take-while (fn [l] (not= l '+)) x)))
(defn augend [x] (if (= (length x) 3)
(nth x 2)
(let [rst (rest (drop-while (fn [l] (not= l '+)) x))]
(if (= (length rst) 1) (first rst) rst))))
(defn product? [x] (and (seq? x) (not (sum? x)) (= (second x) '*)))
(def multiplier first)
(defn multiplicand [x] (if (> (length x) 3) (drop 2 x) (nth x 2)))
Exercise 2.59
(defn element-of-set?
"return whether x is a member of the set, using unordered list"
[x set]
(cond (empty? set) false
(= x (first set)) true
:otherwise (recur x (rest set))))
(defn adjoin-set
"add x to set if it is not already a member, using unordered list"
[x set]
(if (element-of-set? x set)
set
(cons x set)))
(defn intersection-set
"compute intersection of 2 sets using unordered lists"
[set1 set2]
(cond (or (empty? set1) (empty? set2)) '()
(element-of-set? (first set1) set2)
(cons (first set1)
(intersection-set (rest set1) set2))
:otherwise (intersection-set (rest set1) set2)))
(defn union-set
"compute union of 2 sets using unordered lists"
[set1 set2]
(cond (empty? set1) set2
(empty? set2) set1
(element-of-set? (first set1) set2) (union-set (rest set1) set2)
:otherwise (cons (first set1)
(union-set (rest set1) set2))))
Exercise 2.60
(defn element-of-set?
"return whether x is a member of the set, using unordered list"
[x set]
(cond (empty? set) false
(= x (first set)) true
:otherwise (recur x (rest set))))
(def adjoin-set cons)
(defn intersection-set
"compute intersection of 2 sets using unordered lists"
[set1 set2]
(cond (or (empty? set1) (empty? set2)) '()
(element-of-set? (first set1) set2)
(cons (first set1)
(intersection-set (rest set1) set2))
:otherwise (intersection-set (rest set1) set2)))
(def union-set concat)
Allowing duplicates, the implementations of element-of-set? and intersection-set are unchanged. Adjoin-set and union-set become primitive list operations cons and concat, and hence should operate in O(1) and O(N) time, respectively. If duplicates accumulate, however, N no longer reflects the size of the mathematical set abstraction, but rather the size of the underlying list, including the duplicates. So the speed of element-of-set?, intersection-set, and union-set will be adversely affected.
I might use this set representation in applications where it is not important to know the true size of the set, or ones where the queries are primarily checking for set membership, not interating over its members. In reality, I'd probably only use this in scenarios where I already know there are no duplicates because of the way the sets are built up. Even then I'd be more likely to use a bit array if the members are small natural numbers.
Exercise 2.61
(defn element-of-set?
"return whether x is a member of the set, using ordered list representation"
[x set]
(cond (empty? set) false
(= x (first set)) true
(< x (first set)) false
:otherwise (recur x (rest set))))
(defn intersection-set
"return intersection of two sets, using ordered list representation"
[set1 set2]
(if (or (empty? set1) (empty? set2))
'()
(let [x1 (first set1) x2 (first set2)]
(cond (= x1 x2) (cons x1 (intersection-set (rest set1) (rest set2)))
(< x1 x2) (intersection-set (rest set1) set2)
:otherwise (intersection-set set1 (rest set2))))))
(defn adjoin-set
"return adjoined-set produced from adding member to set if not present"
[x set]
(cond (empty? set) (list x)
(= x (first set)) set
(> x (first set)) (cons (first set) (adjoin-set x (rest set)))
:otherwise (cons x set)))
For the unordered representation, adjoin-set would visit every member of the list, for adjoining an element not present, and then 1 constant operation to prepend the element. For elements already present, it would visit half the list, on average, to determine that the element is already present, and then need no additional steps.
For the ordered representation, for adjoining an element not present, it would visit half the list, on average, before finding its insertion point, and then a constant operation to insert, so approximately half the number of steps compared to the unordered representation. For elements already present, though, it still visits half the list, on average, determining that the element is already present. So the "half as many steps" only applies to insertion of an element that is not already present.
Exercise 2.62
(defn union-set
"produce union of two sets represented as ordered lists"
[set1 set2]
(cond (empty? set1) set2
(empty? set2) set1
:otherwise (let [x1 (first set1) x2 (first set2)]
(cond (= x1 x2) (union-set (rest set1) set2)
(< x1 x2) (cons x1 (union-set (rest set1) set2))
:otherwise (cons x2 (union-set set1 (rest set2)))))))
The number of steps taken is equal to (a constant factor plus) the sum of the sizes of the 2 lists, since on each step 1 of the lists gets reduced in size by 1. So this executes in θ(n).
Exercise 2.63
I chose to use a node struct here, a little cleaner and probably faster.
(defstruct node :left-branch :entry :right-branch)
(def entry (accessor node :entry))
(def left-branch (accessor node :left-branch))
(def right-branch (accessor node :right-branch))
(defn make-tree
"build a tree from its entry, left, and right branches"
[entry left right]
(struct node left entry right))
(defn element-of-set?
[x set]
(cond (nil? set) false
(= x (entry set)) true
(< x (entry set)) (element-of-set? x (left-branch set))
:otherwise (element-of-set? x (right-branch set))))
(defn adjoin-set
[x set]
(cond (nil? set) (make-tree x nil nil)
(= x (entry set)) set
(< x (entry set)) (make-tree (entry set)
(adjoin-set x (left-branch set))
(right-branch set))
:otherwise (make-tree (entry set)
(left-branch set)
(adjoin-set x (right-branch set)))))
(defn tree->list-1
[tree]
(if (nil? tree)
'()
(concat (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))
(defn tree->list-2
[tree]
(defn copy-to-list [tree result-list]
(if (nil? tree)
result-list
(recur (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list)))))
(copy-to-list tree '()))
Assuming there are no side-effects, and the trees are all well-formed, both procedures should return the same result for every tree: an ordered list of the contents of the tree. An ordered list of integers can be represented with a number of tree shapes, however, these multiple tree shapes all map back to the same identical ordered list of integers.
tree->list-2 has a slower order of growth of stack memory, compared to tree->list-1. tree->list-1 has a deferred concat that must occur on every level, so it cannot benefit from tail call optimization. tree->list-2 cannot fully benefit from tail call optimization since there are 2 trees to recurse down in the general case, however it does perform tail call optimization on the left subtree, so it should have a slower memory growth rate, especially if the tree is unbalanced towards the left.
Both processes should have the same θ(n) growth rate in terms of number of steps required, however.
Exercise 2.64
(defn partial-tree
[elts n]
(if (= n 0)
(cons nil elts)
(let [left-size (quot (dec n) 2)
left-result (partial-tree elts left-size)
left-tree (first left-result)
non-left-elts (rest left-result)
right-size (- n (inc left-size))
this-entry (first non-left-elts)
right-result (partial-tree (rest non-left-elts) right-size)
right-tree (first right-result)
remaining-elts (rest right-result)]
(cons (make-tree this-entry left-tree right-tree) remaining-elts))))
(defn list->tree [elements]
(first (partial-tree elements (length elements))))
This works via recursive calls to partial-tree. At each level in partial-tree, it further partitions its partition of the list, by subtracting out one for the node entry and evenly dividing the remainder as closely as possible between left and right branches, for which it further calls down into partial-tree, passing the new (sub-)partitions, and then building the result tree from the results of these recursive calls, along with the entry element.
list->tree produces for list (1 3 5 7 9 11) a tree with this structure:
5
/ \
/ \
/ \
1 9
\ / \
3 7 11
The order of growth in the number of steps required by list->tree to convert n elements is θ(n). Each element is processed exactly once, and everything else are constant factors.
Exercise 2.65
(defn union-ordered-list
"produce union of two sets represented as ordered lists"
[set1 set2]
(cond (empty? set1) set2
(empty? set2) set1
:otherwise (let [x1 (first set1) x2 (first set2)]
(cond (= x1 x2) (union-ordered-list (rest set1) set2)
(< x1 x2) (cons x1 (union-ordered-list (rest set1) set2))
:otherwise (cons x2 (union-ordered-list set1 (rest set2)))))))
(defn intersection-ordered-list
"return intersection of two sets, using ordered list representation"
[set1 set2]
(if (or (empty? set1) (empty? set2))
'()
(let [x1 (first set1) x2 (first set2)]
(cond (= x1 x2) (cons x1 (intersection-ordered-list (rest set1) (rest set2)))
(< x1 x2) (intersection-ordered-list (rest set1) set2)
:otherwise (intersection-ordered-list set1 (rest set2))))))
(defn union-set
"order-N union of 2 sets implemented as balanced binary trees"
[set1 set2]
(let [l1 (tree->list-2 set1) l2 (tree->list-2 set2)]
(list->tree (union-ordered-list l1 l2))))
(defn intersection-set
"order-N intersection of 2 sets implemented as balanced binary trees"
[set1 set2]
(let [l1 (tree->list-2 set1) l2 (tree->list-2 set2)]
(list->tree (intersection-ordered-list l1 l2))))
This uses the θ(n) results from several previous exercises, including the functions to compute intersection and union of sets represented as ordered lists. So we transform the balanced tree representation into ordered list representation using a θ(n) function, perform the intersection or union on these ordered lists using a θ(n) function, and then transform the resulting ordered list back into a balanced binary tree via another θ(n) function. The result of a constant number of θ(n) functions is itself θ(n).
Exercise 2.66
Using getKey instead of key because key is already reserved in core Clojure.
(defn lookup
"lookup key in a set of records, structured as a binary tree"
[given-key set-of-records]
(cond (nil? set-of-records) false
(= given-key (getKey (entry set-of-records))) (entry set-of-records)
(< given-key (getKey (entry set-of-records))) (recur given-key (left-branch set-of-records))
:otherwise (recur given-key (right-branch set-of-records))))
Exercise 2.67
Back to using simple list representations for the Huffman exercises.
(defn make-leaf [symbol weight] (list 'leaf symbol weight))
(defn leaf? [object] (= (first object) 'leaf))
(defn symbol-leaf [x] (second x))
(defn weight-leaf [x] (nth x 2))
(def left-branch first)
(def right-branch second)
(defn symbols
"return symbols for a Huffman tree"
[tree]
(if (leaf? tree)
(list (symbol-leaf tree))
(nth tree 2)))
(defn weight
"return weight for a Huffman tree"
[tree]
(if (leaf? tree)
(weight-leaf tree)
(nth tree 3)))
(defn make-code-tree
"make a Huffman tree by joining left and right subtrees"
[left right]
(list left
right
(concat (symbols left) (symbols right))
(+ (weight left) (weight right))))
(defn choose-branch
[bit branch]
(cond (= bit 0) (left-branch branch)
(= bit 1) (right-branch branch)
:otherwise (error "bad bit -- CHOOSE-BRANCH" bit)))
(defn decode
"decode stream of 1s and 0s using the supplied Huffman tree"
[bits tree]
(defn decode-1
[bits current-branch]
(if (empty? bits)
'()
(let [next-branch (choose-branch (first bits) current-branch)]
(if (leaf? next-branch)
(cons (symbol-leaf next-branch)
(decode-1 (rest bits) tree))
(decode-1 (rest bits) next-branch)))))
(decode-1 bits tree))
(defn adjoin-set
[x set]
(cond (empty? set) (list x)
(< (weight x) (weight (first set))) (cons x set)
:otherwise (cons (first set)
(adjoin-set x (rest set)))))
(defn make-leaf-set
[pairs]
(if (empty? pairs)
'()
(let [pair (first pairs)]
(adjoin-set (make-leaf (first pair) (second pair))
(make-leaf-set (rest pairs))))))
(def sample-tree
(make-code-tree (make-leaf 'A 4)
(make-code-tree
(make-leaf 'B 2)
(make-code-tree (make-leaf 'D 1)
(make-leaf 'C 1)))))
(def sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))
This sample message+tree produces (A D A B B C A) when sent through the decoder.
Exercise 2.68
(defn symbol-member
"return whether a symbol is a member of a specified list of symbols"
[symbol symbols]
(cond (empty? symbols) false
(= symbol (first symbols)) true
:otherwise (recur symbol (rest symbols))))
(defn encode-symbol
"encode a single symbol using the specified Huffman tree"
[symbol tree]
(if (not (symbol-member symbol (symbols tree)))
(error "Invalid symbol not contained in tree--" symbol)
(if (leaf? tree)
'()
(if (symbol-member symbol (symbols (left-branch tree)))
(cons 0 (encode-symbol symbol (left-branch tree)))
(cons 1 (encode-symbol symbol (right-branch tree)))))))
(defn encode
"encode a message using the specified Huffman tree"
[message tree]
(if (empty? message)
'()
(concat (encode-symbol (first message) tree)
(encode (rest message) tree))))
user=> (encode '(A D A B B C A) sample-tree)
(0 1 1 0 0 1 0 1 0 1 1 1 0)
The resulting encoding does exactly match the code given in exercise 2.67.
Exercise 2.69
(defn successive-merge
"perform successive merge of smallest weight nodes to build up Huffman tree"
[leaves]
(cond (empty? leaves) nil
(= (length leaves) 1) (first leaves)
:otherwise (recur (adjoin-set (make-code-tree (first leaves) (second leaves))
(drop 2 leaves)))))
(defn generate-huffman-tree
"generate Huffman tree from a list of symbol-frequency pairs"
[pairs]
(successive-merge (make-leaf-set pairs)))
Exercise 2.70
(def sample-tree2_70
(generate-huffman-tree (list '(A 2) '(BOOM 1) '(GET 2) '(JOB 2)
'(NA 16) '(SHA 3) '(YIP 9) '(WAH 1))))
(def sample-coding2_70
(encode (list 'GET 'A 'JOB
'SHA 'NA 'NA 'NA 'NA 'NA 'NA 'NA 'NA
'GET 'A 'JOB
'SHA 'NA 'NA 'NA 'NA 'NA 'NA 'NA 'NA
'WAH 'YIP 'YIP 'YIP 'YIP 'YIP 'YIP 'YIP 'YIP 'YIP
'SHA 'BOOM)
sample-tree2_70))
user=> sample-coding2_70
(1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0
1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1
1 0 1 1)
user=> sample-tree2_70
((leaf NA 16) ((leaf YIP 9) (((leaf A 2) ((leaf WAH 1) (leaf BOOM 1) (WAH BOOM)
2) (A WAH BOOM) 4) ((leaf SHA 3) ((leaf JOB 2) (leaf GET 2) (JOB GET) 4) (SHA JO
B GET) 7) (A WAH BOOM SHA JOB GET) 11) (YIP A WAH BOOM SHA JOB GET) 20) (NA YIP
A WAH BOOM SHA JOB GET) 36)
Coding this message using the Huffman tree generated by the specified symbol-frequency pairs produced an 84 bit message. Encoding this message via a fixed-length code, we'd use 3 bits per symbol to encode the 8 symbols (assuming the message length is specified externally, not using any delimiter). Therefore this 36-symbol message would require a minimum of 108 bits, using a fixed-length code.
Exercise 2.71
The Huffman tree for an alphabet of n symbols with weights 1, 2, 4, ... 2n-1 will tend to be linear, down one branch, with all the symbols hanging off the opposite branch. For n = 5,
31
/\
/ \
15 16
/\
/ \
7 8
/ \
/ \
3 4
/ \
/ \
1 2
For n = 10,
1023
/ \
/ \
511 512
/ \
/ \
255 256
/ \
/ \
127 128
/ \
/ \
63 64
/\
/ \
31 32
/\
/ \
15 16
/\
/ \
7 8
/ \
/ \
3 4
/ \
/ \
1 2
In such trees, only 1 bit is required to encode the most frequent symbol, and n-1 bits are required to encode the 2 least frequent symbols.
Exercise 2.72
With the relative frequencies from exercise 2.71, for the most frequent symbol, the growth rate varies as θ(n) with the number of symbols, since it has to check the full symbol list at the root, and then checks the almost-full symbol list again on the left branch. For the least frequent symbol, the growth rate varies as θ(n), since there are approximately n levels in the tree, and at each level, the symbol is found in 1 step.
Exercise 2.73
(def *dispatch-map* (hash-map))
(defn build-key [op type] (str op "|" type))
(defn putOp [op type item]
(def *dispatch-map* (assoc *dispatch-map* (build-key op type) item)))
(defn getOp [op type]
(get *dispatch-map* (build-key op type)))
(defn square [x] (* x x))
(defn attach-tag [type-tag contents] (cons type-tag contents))
(defn type-tag [datum]
(if (list? datum)
(first datum)
(error "Bad tagged datum -- TYPE-TAG" datum)))
(defn contents [datum]
(if (list? datum)
(second datum)
(error "Bad tagged datum -- CONTENTS" datum)))
(defn install-rectangular-package []
;; internal procedures
(defn real-part [z] (first z))
(defn imag-part [z] (second z))
(defn make-from-real-imag [x y] (list x y))
(defn magnitude [z]
(Math/sqrt (+ (square (real-part z))
(square (imag-part z)))))
(defn angle [z] (Math/atan2 (imag-part z) (real-part z)))
(defn make-from-mag-ang [r a] (list (* r (Math/cos a)) (* r (Math/sin a))))
;; interface to the rest of the system
(defn tag [x] (attach-tag 'rectangular x))
(putOp 'real-part '(rectangular) real-part)
(putOp 'imag-part '(rectangular) imag-part)
(putOp 'magnitude '(rectangular) magnitude)
(putOp 'angle '(rectangular) angle)
(putOp 'make-from-real-imag 'rectangular (fn [x y] (tag (make-from-real-imag x y))))
(putOp 'make-from-mag-ang 'rectangular (fn [r a] (tag (make-from-mag-ang r a)))))
(defn install-polar-package []
;; internal procedures
(defn magnitude [z] (first z))
(defn angle [z] (second z))
(defn make-from-mag-ang [r a] (list r a))
(defn real-part [z] (* (magnitude z) (Math/cos (angle z))))
(defn imag-part [z] (* (magnitude z) (Math/sin (angle z))))
(defn make-from-real-imag [x y] (list (Math/sqrt (+ (square x) (square y)))
(Math/atan2 y x)))
;; interface to the rest of the system
(defn tag [x] (attach-tag 'polar x))
(putOp 'real-part '(polar) real-part)
(putOp 'imag-part '(polar) imag-part)
(putOp 'magnitude '(polar) magnitude)
(putOp 'angle '(polar) angle)
(putOp 'make-from-real-imag 'polar (fn [x y] (tag (make-from-real-imag x y))))
(putOp 'make-from-mag-ang 'polar (fn [r a] (tag (make-from-mag-ang r a)))))
(defn operator [exp] (first exp))
(defn operands [exp] (rest exp))
(defn deriv [exp var]
(cond (number? exp) 0
(variable? exp) (if (same-variable? exp var) 1 0)
:else ((getOp 'deriv (operator exp)) (operands exp) var)))
(defn install-deriv-package []
;; internal procedures
(defn =number? [exp num] (and (number? exp) (= exp num)))
(defn make-sum [a1 a2]
(cond (=number? a1 0) a2
(=number? a2 0) a1
(and (number? a1) (number? a2)) (+ a1 a2)
:else (list '+ a1 a2)))
(def addend first)
(def augend second)
(defn make-product [m1 m2]
(cond (or (=number? m1 0) (=number? m2 0)) 0
(=number? m1 1) m2
(=number? m2 1) m1
(and (number? m1) (number? m2)) (* m1 m2)
:else (list '* m1 m2)))
(def multiplier first)
(def multiplicand second)
(defn make-exponentiation [b e]
(cond (=number? e 0) 1
(=number? e 1) b
:else (list '** b e)))
(def base first)
(def exponent second)
(defn deriv-sum [exp var] (make-sum (deriv (addend exp) var)
(deriv (augend exp) var)))
(defn deriv-product [exp var]
(make-sum
(make-product (multiplier exp)
(deriv (multiplicand exp) var))
(make-product (deriv (multiplier exp) var)
(multiplicand exp))))
(defn deriv-exponentiation [exp var]
(make-product (make-product (exponent exp)
(make-exponentiation (base exp) (make-sum (exponent exp) -1)))
(deriv (base exp) var)))
;; interface to the rest of the system
(putOp 'deriv '+ deriv-sum)
(putOp 'deriv '* deriv-product)
(putOp 'deriv '** deriv-exponentiation))
(defn apply-generic [op & args]
(let [type-tags (map type-tag args)
proc (getOp op type-tags)]
(if proc
(apply proc (map contents args))
(error "No method for these types -- APPLY-GENERIC" (list op type-tags)))))
(defn real-part [z] (apply-generic 'real-part z))
(defn imag-part [z] (apply-generic 'imag-part z))
(defn magnitude [z] (apply-generic 'magnitude z))
(defn angle [z] (apply-generic 'angle z))
(defn make-from-real-imag [x y]
((getOp 'make-from-real-imag 'rectangular) x y))
(defn make-from-mag-ang [r a]
((getOp 'make-from-mag-ang 'polar) r a))
Deriv was transformed into data-directed style by rewriting the basic derivative procedure to handle as special cases derivation of simple numbers and variables, and dispatch all other expressions to the dispatch table according to its operation. In this version, the operation is removed in the process of dispatch.
Predicates number? and same-variable? and variable? cannot be assimilated into the data dispatch because these are special cases -- they are not prefixed with an operator tag, in the way that all the other dispatched operations are. So we handle these beforehand as special cases.
If the order of the arguments to getOp were reversed, to (get (operator exp) 'deriv), then the arguments to putOp to insert the various deriv operations would need to have their first 2 arguments reversed, accordingly.
Exercise 2.74
(def *dispatch-map* (hash-map))
(defn getKey [op type] (str op "|" type))
(defn get-record
"return specified employee's record found from specified personnel file, if found, else nil"
[name personnel-file]
(let [record-type (first personnel-file)
contents (rest personnel-file)
lookup-key (getKey 'lookup-employee record-type)
lookupfn (get *dispatch-map* lookup-key)]
(lookupfn name contents)))
(defn get-salary
"return salary from an employee's record, from any personnel file"
[rec]
(let [record-type (first rec)
contents (rest rec)
lookup-key (getKey 'lookup-salary record-type)
contents (rest rec)
lookupfn (get *dispatch-map* lookup-key)]
(lookupfn contents)))
(defn find-employee-record
"search for employee record across all personnel files, if found, else nil"
[name personnel-files]
(if (empty? personnel-files)
nil
(let [file (first personnel-files)
rec (get-record name file)]
(if (nil? rec)
(recur name (rest personnel-files))
rec))))
This implementation relies upon each personnel file being structured as a sequence with its first element being a type tag. Each division should install into the global *dispatch-map*, keyed by "op|type", the various operations applying to that type of personnel file and its related sub-records (e.g., employee record).
When Insatiable takes over a new company, a new set of functions adhering to the standard interface need to be defined, for the new division, and an install package that installs these functions into the global *dispatch-map* under the correct corresponding keys. Also, the division personnel file will need to be added to the global list that find-employee-record gets called with (and that any other cross-division functions use).
Exercise 2.75
(defn make-from-mag-ang
"make complex number from its magnitude/angle, using message passing"
[mag ang]
(fn [op]
(cond (= op 'real-part) (* mag (Math/cos ang))
(= op 'imag-part) (* mag (Math/sin ang))
(= op 'magnitude) mag
(= op 'angle) ang
:else (error "Unknown op -- MAKE-FROM-MAG-ANG" op))))
Exercise 2.76
For systems employing generic operations with explicit dispatch, when we add new types, every one of the generic operations must be modified to add the appropriate handling for the new type. When we want to add a new operation to this system, it needs to have case handling for every existing type, to dispatch to the correct implementation for that type.
For systems employing data-directed style, when we add new types, new implementation methods need to get written for each generic operation, and an install package needs to get written to add these all into the global dispatch map. When we add a new operation to this type of system, all the existing types need to have implementations created, and added to their install package.
For systems employing message-passing style, when we add new types, their dispatch procedure needs to implement all the existing operations. When we add new operations, these need to get implemented as additions to the dispatch procedures for all the existing types.
For systems in which new types must often be added, message-passing style seems most appropriate since adding new types is an additive operation. For systems in which new operations must often be added, generic operations with explicit dispatch seems the best choice, since again this is an additive procedure here.
Exercise 2.77
Alyssa's suggestion works because every operation defined in terms of apply-generic takes the type specifier from the front of the list and uses it to lookup the operation. So we can add the lookup for the complex magnitude, and it will in turn delegate to apply-generic magnitude again, peeling off the rectangle next time, calling apply-generic twice altogether.
When magnitude is evaluated, (apply-generic 'magnitude z) is substituted. In the process of evaluating this, type-tags are generated by mapping function type-tag onto z, then getOp is called, passing in operation 'magnitude and the type-tags (complex). getOp returns function magnitude, which is bound to proc. apply-generic continues, applying proc (magnitude) to the result of applying "contents" to z (which produces (rectangular 3 4)). So the same outer magnitude, defined in terms of apply-generic gets called a second, inner time.
When this inner call of magnitude is evaluated, (apply-generic 'magnitude (rectangular 3 4)) is substituted. In the process of evaluating this, type-tags are generated by mapping function type-tag to produce (rectangular), then getOp is called, passing in operation 'magnitude and the type-tag (rectangular). getOp returns private function magnitude, defined in the rectangular package, which is bound to proc. apply-generic continues, applying proc (magnitude) to the result of applying "contents", which produces (3 4).
This innermost call of (rectangular) magnitude calls real-part and imag-part private functions to extract the 3 and 4, respectively, and calls square on each, then + on those results, and then finally passes that sum to sqrt.
Exercise 2.78
(defn attach-tag [type-tag contents]
(if (and (= type-tag 'clojure-number) (number? contents))
contents
(cons type-tag contents)))
(defn type-tag [datum]
(cond (number? datum) 'clojure-number
(list? datum) (first datum)
:else (error "Bad tagged datum -- TYPE-TAG" datum)))
(defn contents [datum]
(cond (number? datum) datum
(list? datum) (second datum)
:else (error "Bad tagged datum -- CONTENTS" datum)))
Exercise 2.79
;; to be included in the complex package
(putOp 'equ? '(complex complex)
(fn [x y] (and (= (real-part x) (real-part y))
(= (imag-part x) (imag-part y)))))
;; to be included in the clojure-number package
(putOp 'equ? '(clojure-number clojure-number)
(fn [x y] (= x y)))
;; to be included in the rational package
; assumes rationals always stored in normalized form
(putOp 'equ? '(rational rational)
(fn [x y] (and (= (numer x) (numer y))
(= (denom x) (denom y)))))
(defn equ? [x y] (apply-generic 'equ? x y))
Exercise 2.80
;; to be included in the complex package
(putOp '=zero? '(complex)
(fn [x] (and (= 0 (real-part x)) (= 0 (imag-part x)))))
;; to be included in the clojure-number package
(putOp '=zero? '(clojure-number)
(fn [x] (= 0 x)))
;; to be included in the rational package
; assumes 0/0 should not count as zero
(putOp '=zero? '(rational)
(fn [x] (and (= (numer x) 0)
(not= (denom x) 0))))
(defn =zero? [x] (apply-generic '=zero? x))
Exercise 2.81
With Louis' coercion procedures installed, if apply-generic is called with two arguments of type clojure-number or two arguments of type complex for an operation that is not found in the table for those types, it will go into an infinite loop. It will perform the dummy coercion from t1->t2 and then call back into apply-generic again with the coerced argument, doomed to repeat the same steps over and over again.
Louis is not correct that arguments of the same type need to be coerced. If the arguments are of the same type, and a corresponding operation procedure is defined, the procedure is applied to the arguments. Otherwise, if no such procedure is defined, coercion is pointless and apply-generic correctly fails with a "No method" error.
Modifying apply-generic to not try coercion if the two arguments have the same type:
(defn apply-generic
[op & args]
(let [type-tags (map type-tag args)
proc (getOp op type-tags)]
(if proc
(apply proc (map contents args))
(if (= (length args) 2)
(let [type1 (first type-tags)
type2 (second type-tags)
a1 (first args)
a2 (second args)]
(if (= type1 type2)
(error "No method for these types"
(list op type-tags))
(let [t1->t2 (get-coercion type1 type2)
t2->t1 (get-coercion type2 type1)]
(cond t1->t2 (apply-generic op (t1->t2 a1) a2)
t2->t1 (apply-generic op a1 (t2->t1 a2))
:else (error "No method for these types"
(list op type-tags))))))
(error "No method for these types"
(list op type-tags))))))
Exercise 2.82
(defn apply-generic
[op & args]
(let [type-tags (map type-tag args)
proc (getOp op type-tags)]
(if proc
(apply proc (map contents args))
(do (defn can-coerce-all-args [totype type-tags]
(cond (empty? type-tags) true
(nil? (get-coercion (first type-tags) totype)) false
:else (recur totype (rest type-tags))))
(defn coerce-args [totype type-tags args]
(cond (empty? args) '()
(= totype (first type-tags))
(cons (first args)
(coerce-args totype (rest type-tags) (rest args)))
:else (let [t1->t2 (get-coercion (first type-tags) totype)]
(cons (t1->t2 (first args))
(coerce-args totype
(rest type-tags)
(rest args))))))
(defn try-coerce-args [type-tags args]
(defn try-coerceR [totype-list type-tags args]
(cond (empty? totype-list) nil
(can-coerce-all-args (first totype-list) type-tags)
(coerce-args (first totype-list) type-tags args)
:else (recur (rest totype-list) type-tags args)))
(try-coerceR type-tags type-tags args))
(let [coerced (try-coerce-args type-tags args)]
(if (nil? coerced)
(error "No method for these types"
(list op type-tags))
(eval (concat '(apply-generic op) coerced))))))))
This wouldn't handle every possible case. For example, if there is an operation defined to raise a real number to an integral power, and we pass in two integers, trying to coerce both integers to real numbers would still not match the operation. In order to correctly handle situations such as this, we would have to try all combinations of coercion (not just all-arguments-the-same) to see if any yield a match from the dispatch table.
Exercise 2.83
;; to be included in the clojure-number package
(putOp 'raise '(clojure-number)
(fn [x] (make-rational x 1)))
;; to be included in the rational package
(putOp 'raise '(rational)
(fn [x] (make-real x)))
;; to be included in the real package
(putOp 'raise '(real)
(fn [x] (make-from-real-imag x 0)))
(defn raise [x]
(apply-generic 'raise x))
Exercise 2.84
(defn height-of-type [x]
(let [type (type-tag x)]
(cond (= type 'clojure-number) 1.0
(= type 'rational) 2.0
(= type 'real) 3.0
(= type 'complex) 4.0
:else (error "unhandled type" (list x)))))
(defn raise-to-height
"raise x to the specified height, if below, via coercion"
[x height]
(if (< (height-of-type x) height)
(recur (raise x) height)
x))
(defn apply-generic
[op & args]
(let [type-tags (map type-tag args)
proc (getOp op type-tags)]
(if proc
(apply proc (map contents args))
(let [maxheight (max (map height-of-type type-tags))
coerced (map (fn [x] (raise-to-height x maxheight)))]
(if (nil? coerced)
(error "No method for these types"
(list op type-tags))
(eval (concat '(apply-generic op) coerced)))))))


EasyImage is a promise-based image processing module for Node.js, it is built on top of ImageMagick, so make sure ImageMagick is installed on your system.
EasyImage 3 is only compatible with NodeJS 4 or greater.
$ npm install --save easyimage
For NodeJS 0.12, use EasyImage 2
$ npm install --save easyimage@2
Get info about an image.
import {info} from "easyimage";
try {
const imageInfo = await info("/path/to/image.jpg");
} catch (e) {
console.log("Error: ", e);
}
Convert an image from JPG to PNG.
import {convert} from "easyimage";
try {
await convert({
src: "/path/to/source.jpg",
dst: "/path/to/dest.png",
});
} catch (e) {
console.log("Error: ", e);
}
Create a thumbnail.
import {thumbnail} from "easyimage";
try {
const thumbnailInfo = await thumbnail({
src: "/path/to/source.jpg",
width: 100,
height: 100,
});
console.log("Thumbnail is at: " + thumbnailInfo.path);
} catch (e) {
console.log("Error: ", e);
}
The EasyImage module is ES6 compatible. You can import just the commands that you will need.
Every command which takes an options object which extends from IBaseOptions. You can use
any of the parameters defined on IBaseOptions
. For example, to prevent EasyImage from auto-orientating your image, you can pass autoOrient: false
on any
command.
Every command must have a src
parameter. If you do not specify a dst
, then a random file will be created. Be sure to clean up randomly created files by
either moving them to permanent storage, or deleting them. Some commands have other required options.
See the Docs for all available options for each command.
convert
The convert() command can convert an image file from one type to another.
crop
The crop() command will crop an image to the specified size.
resize
The resize() command will resize an image to the specified size.
rescrop
The rescrop() command will resize and crop an image to the specified size.
rotate
The rotate() command will rotate an image by the specified number of degrees.
thumbnail
The thumbnail() command will create a thumbnail of the specified image.
In addition to the above commands, there are three other commands available.
info
The info() command will give you details about an image file.
execute
The execute() command allows you directly run ImageMagick with your own tool and arguments. It will handle calling the appropriate ImageMagick version, and
return the raw stdout
and stderr
to you.
getImageMagickVersion
The getImageMagickVersion() command will return the detected version of ImageMagick.
There are 5 different types of errors that can be thrown.
BadDestinationError
ImageMagickMissingError
MissingExtensionError
MissingOptionsError
UnsupportedError
Which allows you to catch specific errors.
import {convert, MissingOptionsError} from "easyimage";
async function shouldError() {
try {
await convert({});
console.log("I should not show");
} catch (MissingOptionsError e) {
console.log("I should show");
} catch (Error e) {
console.log("I should not show either");
}
}
Copyright (c) 2015 Hage Yaapa <http://www.hacksparrow.com>
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Generated using TypeDoc


Go to the content directory?


File system implementation of core package interfaces, based on com.adaptris.fs package.
core
com.adaptris.fs


[1] Adams, H., Zinsmeister, N., Robinson, D. (2020). Uniswap v2 Core. Retrieved from https://uniswap.org/whitepaper.pdf
[2] Martinelli, F., Mushegian, N. (2019). A non-custodial portfolio manager, liquidity provider, and price sensor. Retrieved from https://balancer.finance/whitepaper
[3] Egorov, M. (2019). StableSwap - efficient mechanism for Stablecoin liquidity. Retrieved from https://www.curve.fi/stableswap-paper.pdf
[4] Leshner, R., Hayes, G. (2019). Compound: The Money Market Protocol. Retrieved from https://compound.finance/documents/Compound.Whitepaper.pdf
[5] Aave Protocol Whitepaper v1.0. (2020). Retrieved from https://github.com/aave/aave-protocol/blob/master/docs/Aave_Protocol_Whitepaper_v1_0.pdf
[6] The Maker Protocol: MakerDAO's Multi-Collateral Dai (MCD) System. (2020). Retrieved from https://makerdao.com/en/whitepaper/#in-mcd-we-trust
[7] Angeris, G., Chitra, T. (2020). Improved Price Oracles: Constant Function Market Makers. Retrieved from https://web.stanford.edu/~guillean/papers/constant_function_amms.pdf
[8] Angeris, G., Evans, A., & Chitra, T. (2020). When does the tail wag the dog? Curvature and market making. arXiv preprint arXiv:2012.08040.
[9] S. Ellis, A. Juels, and S. Nazarov. Chainlink: A decentralized oracle network. 2017.


OpenHDS - Submissions
No. of current submissions:
Available Exports
Found existing recent export.
Click below to generate a new CSV-file from the current submissions:
No submissions available for export!