Managing List Data

This page does not belong in Unit 7! The stuff about sorting should be rewritten functionally, and the rest of it shouldn't be in the curriculum at all, imho. --bh
For more development ideas: see also Shuffling Cards from Zeph Grunschlag in NY and also Looping Puzzle
From michael (via GH):
This paragraph doesn't really say anything important or memorable. Just jump into the FYTD. --bh

Lists are essential to efficient data management. Lists can be counted, added to, removed from, selected from, searched in, and sorted. In this lesson, you will refine your Shopping List App, and you will explore common programming tasks related to lists: indexing, swapping, and sorting.

  1. Review your "U2L2-ShoppingList" project from Shopping List App:
      Contains will be helpful here.
    1. If you didn't write code for the "Search" button, do it now. Clicking the "Search" button should prompt the user for a search term and then tell the user whether that item is already on the list (but not add the item). If you already wrote code for "Search" button, review your code and either try to improve it or help someone else create their own.
    2. Write a script for the "Delete Item" button that removes an item from the list if you haven't already.
      3. 1c: Why? --bh
    3. Try re-writing your "Add Item" script a different way:
        Save Your Work
      • either using set and in front of
      • or using the add block
      Talk with Your Partner How do these two methods differ?
      4. For each and insert will be helpful here.
      Here's how we do it in the list utilities library:
    4. Perhaps you coded your "Add Item" button to check to see if the item you want to add is already on the list so you don't create duplicates. Either way, create a "Clean Up List" button that removes any duplicate items from the list. Here are some instructions:
      1. Save this image to your computer: Clean Up List button
      2. Open and add a new sprite to your U3L1-ShoppingList project, call the sprite "Clean Up", and import the new button image on the Costumes tab for that sprite.
      3. Create a reporter uniques that takes a list as input and reports a list of each unique item in the original list.
        4. We've known what this endnote says since U1.--bh
        Reporter blocks output (report) information based on the inputs, but they don't change the values stored in the input variable(s).
      4. Code the "Clean Up List" button to set the shopping list to a list of the unique items in shopping list.
      5. Save your work

Using an Index Variable

The content in this section was adapted from a former U3 investigation: Processing a Sentence
Is this in the framework or something? Because the way I'd write spell word is

Part of what makes lists so powerful is that lists are ordered and each item in the list has an index number that you can use to refer to that particular item. But using an index variable to process a bunch of values is not specific to lists! Creating an index from scratch is fairly common in programming and worth getting comfortable with.

This block says each of the items in a list:
read through list (list) block definition

The block says all of the letters in a sentence:
spell word (word) block definition

Since there is no for each letter block that indexes strings of characters as if they were in a list, we must create an index variable and increase it by 1 (increment it) each time through the loop.

  1. Talk with Your Partner Read through each line of the spell word script above, and discuss how it works.
  2. Modify the script above to make the sprite say the following:
    When writing a script, if you already have a similar script, then you can:
    • Either duplicate the existing script and modify it for the new functionality
    • Or create a more general script that can be used for both purposes.
    1. Every other letter in the word
    2. Every third letter
    3. All the letters in reverse order
    4. A range of letters (for example, letters 4-7) using either a repeat until or a repeat block
    3. Save your work
DANGER BELOW: See Brian's note. We must actually create, not just imagine, the programs we ask kids to write. Problem b won't work, at least not as specified. Because of the title of this section, I've included the whole section in the warning.

Swapping Variable Contents

  1. Another common programming task is swapping the values of two variables or items in a list. So, it's worth building a custom block (or two—one for variables and one for lists) to get familiar with the idea:
    1. "U3L1-Swap"Create a new project called U3L1-Swap
      2. The page bjc-r/cur/programming/old labs/lists/mutation/mutate-vars.html explains why this won't work!
      A script variable to hold one value aside will be useful here.Talk with Your Partner Discuss how you will use it.
    2. Write a Variables command block called swap that takes two variables as input and swaps their values. For example, if variable1 is 100 and variable2 is 200, and these are inputted into swap, variable1 should then be 200 and variable2 should be 100.
      swap () ()
      3. Command blocks can change the values stored in the input variable(s), but they do not report a value.
    3. Write a Lists command block called swap with that takes two index numbers and a list as input and swaps the two list items with those index numbers. For example, this script swaps the 2nd and 5th items of the list assigned to the variable alphabet:
      set (alphabet) to (list () () () () () () ()), swap (2) with (5) in (alphabet)
      4. Save your work
A note on list block types:
  • List reporters perform some kind of calculation with a list (but generally without changing the list), and they report information, perhaps a modified list.
  • List commands perform some kind of calculation on a list. They may actually change the original list and have no output.
Is this any different from what we already know about commands and reporters? What I think you really want to say here is this:
There are two very different styles of programming: functional programming, in which you mostly use reporters, and compute new values rather than modify values of variables that already exist; and imperative programming, in which you mostly use commands, and change the values of variables all the time. All else being equal, functional programming is better because it leads to fewer bugs and because it's much easier to parallelize. But sometimes it's more efficient or just plain easier to use imperative programming style. In Snap!, because of the way lists are implemented, it's important for efficiency reasons to use a consistent style for any particular list—either always use red command blocks to mutate the list, or always use reporters such as in front of or keep to compute new lists based on the old one.
But it's much too early to say that, which is why this whole page, if it belongs anywhere, belongs in Lab 4.

Sorting a List

(1) This animation goes way too fast to read. (2) Here's how I'd want them to think about selection sort:
... but that's recursive, so if we had to do it in this unit, I guess I'd settle for
... but you can see how much uglier that is. So I'd rather do sorting in U7. PG: Sorting is not appropriate here. It's complicated, the technique should be recursive, and it's not needed.
Selection Sort Animation by Joestape89 at the English language Wikipedia
Credit: Joestape89 at the English language Wikipedia

There are many different algorithms for sorting. Some are more efficient than others. Speed and memory matters a lot more when sorting with larger datasets. A simple sorting algorithm that works well with small datasets is the selection sort method shown right.

White is the original list. Yellow is the sorted list. Red is the current minimum. Blue is the current item being compared to the current minimum.

The double-headed arrow indicates a swap from one place in the list to another. The single-headed arrow indicates that the item that was there did not have to move.

  1. Talk with Your PartnerStudy the selection sort graphic at right. Discuss how this sorting algorithm works.
    2. This seems needlessly complicated. Why not just index of smallest value from (here) to end and always do the swap without even checking whether the two indices are the same?
  2. Imagine you already have a lowest of items after? predicate that takes an index number and a list as inputs and outputs (reports) the following:
    • true if the list item at that index number is less than or equal to all of the items after it
    • false if there is another item that is less than it after it.
  3. Talk with Another PairDiscuss how you could use your swap with and lowest of items after? blocks to build a selection sort script.
  1. "U3L1-SelectionSort"Create a new project called U3L1-SelectionSort
    2. Tough Stuff
  2. Create a lowest of items after? predicate (as described above). Test it with a several items in a list of numbers.
    3. Need script pic with result examples of block showing each output.
  3. Build a selection sort script.
    4. This endnote is unnecessary; it just repeats what FYTD #8 just told them! -bh
    Your swap with and lowest of items after? blocks will be useful here.
    The deliberate slight snarkiness of "now would be a good time to save your work" is ruined if you use it routinely at the end of a page. It should be reserved for very occasional use in places mid-page where they're about to introduce a horrible bug in the service of some further enhancement of their program. Also I just noticed that "now would be" has become "now is" which also kind of defeats the point. --bh
    Save your work