New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Data Structures and Functional Programming

by: Lacey Collier

Data Structures and Functional Programming CS 3110

Marketplace > Cornell University > ComputerScienence > CS 3110 > Data Structures and Functional Programming
Lacey Collier
GPA 3.84


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 16 page Class Notes was uploaded by Lacey Collier on Saturday September 26, 2015. The Class Notes belongs to CS 3110 at Cornell University taught by Staff in Fall. Since its upload, it has received 9 views. For similar materials see /class/214341/cs-3110-cornell-university in ComputerScienence at Cornell University.

Similar to CS 3110 at Cornell

Popular in ComputerScienence


Reviews for Data Structures and Functional Programming


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/26/15
CS 3110 Fall 2008 Lecture 27 Andrew Myers Logic programming Pattern matching for Java Course wrap up Declarative vs imperative Imperative programming te computer how to change its state to accomplish a result Declarative programming te computer what you want computed without specifying state changes Avoids side e ects enables analysis and optimization functional programming give an expression equal to the desired result logic programming give a logical formula describing what should be true of the result 0 a simple version database queries Logic programming in Prolog Programmer de nes boolean valued predicates Language gures out all ways to make predicates true Example syntax modi ed from Prolog parentX Y lt father X Y eVXVYfatherXYgtparentXY parentXY lt motherXY fatherbob alice Letrueefatherbobalice parentbob X parentX X No siblingXY lt parentZX parentZY fatherbob charlie siblingalice X x x alice charlie O O Concatenatmg IIsts Go apmdkmepm mLLbmanmghbL L1Lz H1ZZT1L2 H1ZZT1L2 I SO L1Lz L3 L3 H1ZZT3 and T1Lz 2T3 join L2 L2 joinHlTl L2 H1T3 lt joinTlL2T3 joinl23 456 X x l23456 joinlX3 4y 12ZW56 X 2 y 56 z 3 W 4 joinlXX YY XXYYY Reversible computation Pattern matching Pattern matching is limited reversible computation Forward let lst xzzyzzrest Backward match lst with xzzyzzrest gt But we can t pattern match unless we know exactly how the data is represented 0 Can39t pattern match on an abstract type 0 This is why 00 languages don39t have pattern matching JMatch Java pattern matching JMatch supports predicate methods with multiple modes capturing directions of computation class List Object head List tail ListObject h List t returns h t head h ampamp tail t ie oListht ltgt oheadh ampamp otait Forward mode creates an object Backward mode pattern matches binds h and t switch lst case Listl ListObject x List rest return Listx frest JMatch logic programming A limited form of logic programming List joinList x List y returnsx returnsy x Listhx tx amp tr jointx y amp result Listhx tr let Listl List2 null joinprefix List y useyhere static Node balanceint color if Rebalancing a red black tree in JMatch color switch case int value ree left Tree right BLACK valueleftright int 2 NodeREDint y NodeREDint xTree aTree bTree c Tree d NodeREDxaNodeREDybcd c NodeREDzNodeREDyabd NodeREDybNodeREDzcdz 2 return NodeRED Y NodeBLACKxabNodeBLACKzcd return Nodecolor value left right Iteration Logic programming has iteration built in class Node implements IntCollection Tree Tree left right int value boolean color X boolean containsint x iterates x alu amp leftcontainsx value l x value ampamp rightcontainsx x Forward mode usual BST lookup Backward mode in order tree traversal foreach treecontainsint x ampamp x lt 10 use x The tree iterator in Java class Treelterator implements lterator Iterator subiterator boolean hasNeXt Object current int state ll states ll 1lterating through left child I 2 Just yielded current node value ll 3 lterating through right child Treelterato 0 r subiterator Treethislefiiterator0 state 39 preloadtlext0 public boolean hasNext0 return hasNext public Object next0 if hasNext throw new NoSuchElementExceptiono 39 ret rrent preloadNextO return ret private vo id preloadNext0 loop while true switch state case 39 ase hasNext true if subiteratorhasNext0 current subiteratornext0 case 2 subiterator Treerightiterator0 state 39 continue loop Comparing iterators class Tree C4 20 m m a lt a C public lEnumeratorltElemgt elements ea Elem e lef Both languages telemenm H l have coroutine yield return e Iterators yield return value foreach Elem e in rightelements CLU yield return public Elem elements iterates result JMatCh foreach Elem e leftelements ld e e alue foreach Elem e rightelements yield e Elem elements iterates result or result lt value ampamp leftcontainsresult r sult value result gt value ampamp ht Conclusions Object oriented languages are incorporating many functional programming language features higher order functions polymorphism lexical scoping better iterators Pattern matching may show up too What was 3110 about Goal better software design and implementation New programming paradigms highemrder functions pattern mahing polymorphism concurrency Specifying functions and data abstractions Reasoning about correctness using speci cations logic Reasoning about performance 39 quotrnrrn 394 I39llir Important data structures and algorithms i lnrhl nl 8853 a r 39 Final exam Dec 18 2 4230pm Olin 155 Open book Cumulative Follow on courses Complexity CS 3810 Understanding programming paradigms and language features CS 4110 CS 6110 Concurrency CS 4410 Language implementation CS 41204121 Algorithms and algorithm design CS 4820 Logic CS 4860 Credits Instructor Andrew Myers TAs K Vikram PS3 Ed McTigue PSZ6 Rick Ducott PS46 Tanya Gupta P55 Consultants Andrew Owens P515 test harness Matt Pokrzywa PS35 Dane Wallinga P545 David Kupiec PS3 Jerzy Hausknecht P56 Matt Paff PSZ6 Don39t miss the tournament Tuesday Dec 9 Upson B17 730pm


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.