Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Useful instantiations of “fix” on non-function types?

Every time I’ve used fix :: (a -> a) -> a, it’s been at the type

((a -> b) -> a -> b) -> a -> b

for some a and b. Is there actually some application of fix where its type parameter is not instantiated to a function type, other than a trivial thing like fix (const 0)? What is the purpose of leaving the signature at its most general?

like image 573
Jon Purdy Avatar asked Jan 20 '15 01:01

Jon Purdy


People also ask

Which of the following is an example of non-functional testing?

An excellent example of non-functional test would be to check how many people can simultaneously login into a software. Non-functional testing is equally important as functional testing and affects client satisfaction.

What is the difference between clear functional and non-functional requirements?

Clear functional and non-functional requirements allow you to reduce development costs and save time. In a nutshell, the difference between functional and non-functional requirements is as follows: Functional requirements drive the application architecture of a system, while non-functional requirements drive the technical architecture of a system.

What are non-functional features?

These features are usually expressed as constraints or criteria that define a level of freedom for developers or users. Although non-functional requirements may seem a bit subtler, they are still as important as functional features, epics, and user stories.

What are the non-functional parameters in software testing?

This non-functional parameter checks a software system interfaces with other software systems. This is checked by Interoperability Testing The extent to which any software system can handles capacity, quantity and response time. The term refers to the ease with which the application can work in different hardware and software configurations.


2 Answers

I don't know if you would regard this example as trivial, but you can use fix directly (without going through a function) to build up data:

repeat :: a -> [a]
repeat x = fix (x:)
like image 171
Cactus Avatar answered Sep 25 '22 14:09

Cactus


There are many examples of building corecursive data with fix. I don't know enough to elaborate on the general theory, but it seems as though any data type that is like a stream, in that you can always output one more value given the stream so far, can be computed with fix without feeding it a function type.

Examples

The simplest example (given in Cactus's answer) is a repeating stream of values, for example

x = [1, 1, 1, 1, 1, 1, 1, 1, ...]

This satisfies the equation

(1:) x = x

and can be produced by

>> fix (1:)
[1,1,1,1,1,1,1,1,1,1,...]

A slightly more complicated example is the natural numbers

n = [0, 1, 2, 3, 4, 5, 6, ...]

which satisfy the equation

0 : map (+1) n = n

and can be produced by

>> fix ((0:) . map (+1))
[0,1,2,3,4,5,6,7,8,9,...]

The factorial numbers can be generated most easily if we look at the pair (n,f) where f is the nth factorial number -

x = [(0,1), (1,1), (2,2), (3,6), (4,24), (5,120), ...]

which are fixed if we take the pair (n,f) to (n+1, f*(n+1)) and then cons (0,1) to the start of the list. So they can be generated by

>> fix $ \xs -> (0,1) : map (\(n,f) -> (n+1,f*(n+1))) xs
[(0,1),(1,1),(2,2),(3,6),(4,24),(5,120),(6,720),(7,5040),...]

The fibonacci numbers can be generated similarly, as in user3237465's answer.

Generalizing the examples

All three examples here are essentially recursive functions transformed into corecursive streams, i.e. they have some initial state s and the values emitted by the stream are s, f s, f (f s) etc for some function f. The general method for doing this is the function iterate

iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)

which can be defined in terms of fix -

iterate f x = x : map f (iterate f x)
            = (x:) . (map f) $ iterate f x
            = fix ((x:) . map f)

So any stream which repeatedly applies a function to some state can be written in terms of fix (though, of course, you could simply use iterate instead of fix -- a particular case of the rule that fix is not necessary in a language which allows recursive let expressions).

Non-stream examples

For an example that isn't a stream, consider binary trees with values at the branches -

data Tree a = Tip | Bin a (Tree a) (Tree a) deriving (Show)

If we want a binary tree whose nodes are labelled in breadth first order, note that we could fix such a tree by taking two copies of itself, and incrementing all of the values in the left- and right-branches by the appropriate amount, as defined by the following function -

fun :: (Num a) => Tree a -> Tree a
fun t = Bin 1 (incr 1 t) (incr 2 t)
  where
    incr n (Bin a l r) = Bin (a+n) (incr m l) (incr m r)
      where
        m = 2 * n

Using a simple function takeLevels to display just the initial portion of the tree, we then compute the fixed point as

>> takeLevels 3 $ fix fun
Bin 1 (Bin 2 (Bin 4 Tip Tip) (Bin 5 Tip Tip)) (Bin 3 (Bin 6 Tip Tip) (Bin 7 Tip Tip))

which is what we wanted.

like image 29
Chris Taylor Avatar answered Sep 26 '22 14:09

Chris Taylor