Creating a very large list in a diagram
I have a list of objects with me. These objects are called WordPairs.
Example: ((WordPair1) (WordPair2))
etc. I have a function that retrieves their confidence values. I want to create another list with their trust values. This list will only contain numbers. At the end of this calculation, I will have a list of numbers that match the list of WordPairs. I know how to create a basic list using cons
. The problem here is that I have 500,000 word pairs and with recursive minuses I would quickly go into a stack overflow.
What could be the solution?
My naive solution is this:
(define (create-conf-list lst)
(define wp (car lst))
(define confidence (tv-conf (cog-tv wp)))
(if (not (null? (cdr lst)))
(cons confidence (create-conf-list (cdr lst)))
'()))
How can this be improved?
PS: I ran into Stack Overflow with this approach. I need a more efficient approach. I cannot think of how to insert tail recursion here.
source to share
This is similar to what you can do with accumulate and reverse, since you want the result in reverse order of what forward accumulation will produce:
(define (helper ls acc)
(define wp (car ls))
(define confidence (tv-conf (cog-tv wp)))
(if (null? (cdr ls))
(reverse acc)
(helper (cdr ls) (cons confidence acc))))
This is tail-recursive, since the recursive case is only a call to the function itself - the result of the recursive call is not used for anything else.
The reversal is necessary because the cons
accumulator builds the list in reverse order.
(You might be tempted to use (append acc (list confidence))
to keep the list in the order you want, but append
it makes it very slow.)
Then you can call it from the "actual" function:
(define (create-conf-list lst)
(helper lst '()))
Or, you can flip the functions into one:
(define (create-conf-list lst)
(define (helper ls acc)
(define wp (car ls))
(define confidence (tv-conf (cog-tv wp)))
(if (null? (cdr ls))
(reverse acc)
(helper (cdr ls) (cons confidence acc))))
(helper lst '()))
Side note:
You are discarding the last item of proxies, but since you are in the optimization phase, I assume you want it.
If this is not what you want, you should fix this error before thinking about optimization.
source to share