Recursion for an insertion function (more Scheme issues)

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Rippy
Posts: 2101
Joined: Sun Jul 22, 2007 11:27 pm UTC
Location: Ontario, Can o' Duh

Recursion for an insertion function (more Scheme issues)

Postby Rippy » Thu Sep 24, 2009 3:01 pm UTC

Yeah, so, really not enjoying Scheme so far. We're getting assignments that I could easily do recursively or dynamically in a language that makes some sense, but it's near impossible to get my head around in Scheme. Well, I guess I'll get the hang of it sometime. Anyway, right now, as part of a function that gives all permutations of a given list of number (1 3 -> (1 3) (3 1) as a basic example), I'm writing a function that inserts a number n everywhere in a given list of numbers. This is what I have:

Code: Select all

;; insert: num (listof num) -> (listof (listof num))
;; inserts a number before, after and between every number in a list
;; Examples:
(check-expect (insert 2 '(3)) '((2 3) (3 2)))
(check-expect (insert 1 '(2 3)) '((1 2 3) (2 1 3) (2 3 1)))

(define (insert n lst)
  (cond
    [(empty? lst) (cons n empty)]
    [else
     (cons (cons n lst)
           (list (cons (first lst) (insert n (rest lst)))))]))


This holds for 2 numbers, but breaks for anything higher. The second example actually gives:

'((1 2 3) (2 (3 1) (1 3)))

So the problem is where I call insert again recursively: It does indeed find every combination of 1 and 3, but it appends both one after the other after 2, instead of putting a 2 in front of each one.

I can't figure out how to get this to work, and it is frustrating as hell. Can anyone give me some tips for getting it to work? I thought I knew recursion just fine, but having to do this with these strange lists is throwing me off.

Thanks!

-Rippy

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: Recursion for an insertion function (more Scheme issues)

Postby stephentyrone » Thu Sep 24, 2009 3:22 pm UTC

First off, do you understand why the code you have is generating the output that it is?
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

Re: Recursion for an insertion function (more Scheme issues)

Postby qbg » Thu Sep 24, 2009 3:29 pm UTC

You want two functions: One that loops through the input list that will add the element at the right position, and one that loops through a given list to insert an element at a given position.

User avatar
TNorthover
Posts: 191
Joined: Wed May 06, 2009 7:11 am UTC
Location: Cambridge, UK

Re: Recursion for an insertion function (more Scheme issues)

Postby TNorthover » Sat Sep 26, 2009 10:04 am UTC

Two functions is a good suggestion unless you're happy with "map". But I'm not sure I'd describe or split them as qbg did. Look at exactly what your last line is doing to expected input in isolation. I think you'll find you need it to do something slightly more complicated.

It's a nice little case for the list monad in Haskell too (though not strictly necessary):

Code: Select all

import Control.Monad

insert :: a -> [a] -> [[a]]
insert n [] = return [n]
insert n (a:as) = do tailInserted <- insert n as
                     return (a:tailInserted)
                  `mplus`
                  return (n:a:as)

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Recursion for an insertion function (more Scheme issues)

Postby Berengal » Sat Sep 26, 2009 11:25 am UTC

The list monad is nice, but you can take it even further. Like working with logarithms in mathematics, working with non-determinism reduces the strength of your algorithms, and the deterministic "insert", inserting an element 'n' everywhere in the list 'xs' and returning the list of all different lists turns into the non-deterministic "insert", inserting an element 'n' anywhere in the list 'xs' and returning just that list (but as a non-deterministic value).

Code: Select all

import Control.Applicative

-- Base case. 'n' inserted into an empty list returns a list of only one element.
-- 'pure' lifts a deterministic value into a non-deterministic one ('return' does the same)
insert n [] = pure [n]

-- Possibly recursive case.
-- Possibly because since it's non-deterministic, we don't know what path it takes, and not all paths recurse.
insert n (x:xs) =
  -- First alternative, 'n' is inserted before any other elements in the list.
  pure (n:x:xs)
  <|> -- "or". Introduces a non-determistic choice
  -- Second alternative, insert 'n' anywhere in the tail of the list, then put the head of the list in front of the result
  fmap (x:) (insert n xs)

-- 'fmap' lifts a function on deterministic values to work on non-deterministic values
-- In this case the function being inserting 'x' (the head of the input list) first in the returned value

The code is basically identical to the monadic code above in terms of what actually happens under the hood. I hope the mindset shown here lights a bulb in your head though, and doesn't thoroughly confuse you.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

dean.menezes
Posts: 135
Joined: Sat Nov 15, 2008 3:47 am UTC

Re: Recursion for an insertion function (more Scheme issues)

Postby dean.menezes » Sun Sep 27, 2009 9:17 pm UTC

Instead of consing, do a map on cons [actually, a map on]

Code: Select all

(lambda (car cdr)
  ((if (pair? cdr) cons list) car cdr))


But map expects a stream of elements, and you only have one element. One way to get around that is to create a circular list of arguments:

Code: Select all

; Muah ha ha ha
(define (insert n lst)
  (cond
   ((null? lst) (list n))
   (else (cons (cons n lst)
          ((lambda (x)
        (set-cdr! x x)
        (map (lambda (car cdr)
          ((if (pair? cdr) cons list) car cdr))
             x
             (insert n (cdr lst))))
      (list (car lst)))))))


But there is another way to do this by editing the function you are mapping on so it only needs one argument.

User avatar
BrainMagMo
Posts: 185
Joined: Tue Jul 22, 2008 6:22 am UTC
Location: Southern California
Contact:

Re: Recursion for an insertion function (more Scheme issues)

Postby BrainMagMo » Fri Oct 02, 2009 10:24 am UTC

Code: Select all

(define (insert n lst)
  (if (null? lst) (cons n '())
      (cons (cons n lst)
            (map (lambda (sublst)
                   (cons (car lst) (if (list? sublst)
                                       sublst
                                       (list sublst))))
                 (insert n (cdr lst))))))

User avatar
TNorthover
Posts: 191
Joined: Wed May 06, 2009 7:11 am UTC
Location: Cambridge, UK

Re: Recursion for an insertion function (more Scheme issues)

Postby TNorthover » Fri Oct 02, 2009 10:33 am UTC

You probably really want:

Code: Select all

(define (insert n lst)
  (if (null? lst) (list (cons n '()))
      (cons (cons n lst)
            (map (lambda (sublst)
                   (cons (car lst) sublst))
                 (insert n (cdr lst))))))

Not only does it simplify the logic, but it presents a more consistent interface: (insert 1 '()) returns a list containing one element -- the only way of inserting 1 into the empty list. I wish scheme had builtin curry though, that lambda seems a little inelegant to me.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Recursion for an insertion function (more Scheme issues)

Postby Xanthir » Fri Oct 02, 2009 1:17 pm UTC

TNorthover wrote:I wish scheme had builtin curry though, that lambda seems a little inelegant to me.

Um, just add it? In CL:

Code: Select all

(defun curry (func &rest args)
    "Returns func with some arguments already filled in.
     Passed args are given to func first, followed by new args."
    (lambda (&rest more-args)
        (apply func (append args more-args))))

You might have to use slightly different functions in Scheme, but the idea is the same. I use currying constantly.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
TNorthover
Posts: 191
Joined: Wed May 06, 2009 7:11 am UTC
Location: Cambridge, UK

Re: Recursion for an insertion function (more Scheme issues)

Postby TNorthover » Fri Oct 02, 2009 1:27 pm UTC

Xanthir wrote:Um, just add it? You might have to use slightly different functions in Scheme, but the idea is the same. I use currying constantly.

I did say builtin. If I was doing a large project I probably would, but for a tiny example like this I think defining concepts beyond the base language is even more awkward than just slotting a lambda in.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 4 guests