• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Alpha_ProgDes

I need functional language algorithm help

4 posts in this topic

First let me say this, this problem is from How To Design Programs, 2nd Edition (Chapter 4, Section 4.5.1).
 
Second, this is not homework. I'm self-learning.
 
Now, I've made two attempts at this problem. First and Second. My issue is that I know I'm doing something wrong. But I don't know what it is. My process of going through the problem is jacked somehow. In the first attempt, the code looks like right. I'm using recursion, following the steps the book has laid out (to the best of my understanding). But the result produced is the answer plus junk. In the second attempt, there is some recursion and helper functions. And the answers are correct. However, the code feels .... wrong. As if I didn't do it the Scheme way. It's like writing C with classes and not idiomatic C++. It's right, but it's wrong.
 
So any tips, hints, pointing in the right direction, would be greatly appreciated.
2

Share this post


Link to post
Share on other sites
Your second (working) solution gets messy after it gets to insert-everywhere/in-one-word.
The approach is fine, you just haven't written it neatly.

- Your argument names are cryptic and sometimes in an illogical order.
- You write extra functions that obscure rather than clarify. For instance, I have no idea what "move-letters" is supposed to do and what arguments it's supposed to take unless I read the code. And when I read the code, I find it's just (append x (list y)). Stuff like this is better inlined.
- You should always nest definitions that are only intended to be used inside another function. It makes the structure of the code far easier to comprehend, plus it often further simplifies code by allowing you to drop any function arguments that are already defined in the outer scope.

I wrote an exact Scala equivalent to your insert-everywhere/in-one-word function but fixed all of the above. I think it looks fine with these changes. Note how the recursive helper has one less argument than yours, and one function even turned into a local definition with no arguments.
def insertEverywhere(c: Char, string: List[Char]) = {
  def recInsert(stringBefore: List[Char], stringAfter: List[Char]): List[List[Char]] = {
    val newWord = stringBefore ::: (c :: stringAfter)
    if (stringAfter.isEmpty) List(newWord)
    else newWord :: recInsert(stringBefore ::: List(stringAfter.head), stringAfter.tail)
  }
  recInsert(Nil, string)
}
Direct Racket translation: :: is cons, ::: is append, head is first, tail is rest, Nil is empty, val is define. Edited by Yrjö P.
1

Share this post


Link to post
Share on other sites

And the scheme/racket version of your code:

 

(define (insert-everywhere c string)
  (local [(define (recursive-insert string-before string-after)
            (local [(define new-word (append string-before (cons c string-after)))]
              (cond
                [(empty? string-after) (list new-word)]
                [else (cons new-word 
                            (recursive-insert 
                              (append string-before (list (first string-after))) 
                              (rest string-after)))])))]
  (recursive-insert empty string)))

(insert-everywhere "w" (list "e" "a" "r"))
Edited by Alpha_ProgDes
2

Share this post


Link to post
Share on other sites

While your code is certainly correct and written in functional style, I would suggest you try to go one step further. Now, it seems that you are 'inlining' different steps into one big step. Functional programming has the advantage of giving the programmer the possibility to clearly distinguish between different 'levels' of operation, each following a certain pattern.

 

For example, let's say I have a list of numbers and want to take the sum of the squares of all uneven numbers. The following Haskell-code (I picked Haskell because even if you are not familiar with it, I believe it is more readable than Scheme, as long as I stay away from some of the more arcane notations) does this in a straightforward manner:

 

bizarreSum :: [Integer] -> Integer
----------------------------------
bizarreSum []     = 0                            -- empty list case
bizarreSum (x:xs)                                -- cons case (head = x, tail = xs)
    | odd x       = x * x + bizarreSum xs        --    head is odd
    | otherwise   = bizarreSum xs

 

But one can distinguish three different steps in this algorithm: first, we filter out the even numbers, then we square every number, and finally, we summate. This can be written as

bizarreSum' :: [Integer] -> Integer
-----------------------------------
bizarreSum' = foldl (+) 0 . map sqr . filter odd

 

 

 

The dot chains the operations together: filtering, mapping, folding. Filter, map and foldl are three well-known patterns, they are in a way higher-level functional loops. In my opinion, it is preferable to try to find these patterns and try to implement your algorithms using them, as you work on a higher level of abstraction.

 

Permutation can then be implemented as a series of mapping operations. My Haskell implementation looks like this:

 

split :: [a] -> [([a], a, [a])]
-------------------------------
split xs = [ (take n xs, xs !! n, drop (n+1) xs)
           | n <- [ 0 .. length xs - 1 ] ]


permutations :: [a] -> [[a]]
----------------------------
permutations [] = [[]]
permutations xs = do (prefix, x, postfix) <- split xs
                     p <- permutations (prefix ++ postfix)
                     return (x : p)

 

The permutations function first splits a list [a(1), a(2), ..., a(n)] up in three parts: a prefix list [a(1)..a(i-1)], an element x=a(i), and a postfix list [a(i+1)..a(n)], for every possible i (this is a map). Then for all permutations p of prefix++postfix (again a map) it prepends x=a(i) to the front of p. So, this is akin to a nested loop, or in our case, a map within a map. In above Haskell code, you can interpret "x <- xs" as "for each x in xs" (it uses monads, which are  a very powerful concept, and I love to explain people about them, but now it is a bit out of scope of this post).

 

In your first attempt, insert-everywhere/in-all-words seems to be wrong:


(insert-everywhere/in-all-words 1 '((2 3)))
'((1 2 3) (1 3 2) (2 1 3) (3 2 1) (3 1 2) (2 3 1))

I don't think it is supposed to generate all permutations of (2 3) in this example. I didn't take the time to inspect your code thoroughly, but I did notice a lot of conds and recursion, which means that you are constantly reimplementing functional building blocks, map in your case.

 

Final note: it is true that bizarreSum' is less memory-efficient than bizarreSum, as each time a new list must be created in memory (however, this does not apply to Haskell as it is a nonstrict language, but in most other languages, this could be an actual issue). However, would performing your own inlining not be a case of premature optimisation? If it is your intention to practice functional programming, I believe it is more important to focus on learning to think on a higher level than to be efficient.

Edited by SamLowry
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0